Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/2250 입력된 이진트리에 대해서 각 노드에 대해 세로위치(열)번호를 매겨서 가장 넓은 레벨을 찾고, 그 너비를 출력하는 문제이다. 풀이 left, rignt값을 가진 노드를 만들고, 노드번호가 0~N-1까지이기 때문에 N크기의 노드 배열을 만들어 트리로 이용했다. -> 루트를 알 수 없기 때문에, 입력받을 때 check배열에 자신,왼쪽자식,오른쪽자식 모두 +1을 했다. 입력을 다 받은 후에 check[root] = 1이고 , root를 제외한 모든 노드는 2이다. 이렇게 루트를 찾았다. 중위순회 : 왼->자신->오 순으로 방문 따라서 트리를 중위순회하여 1부터 하나씩 증가시키며 열번호를 매겼다. 이 때, level값을 이용하여 min_col..

문제 https://www.acmicpc.net/problem/9019 풀이 BFS를 이용했다. 가능한 경우의 수가 0 ~ 9999 까지 였기 때문에, 10000크기의 visited 배열을 만들어 이용했다. 처음에 L과 R을 숫자를 String으로 바꾸어서 만드는 방식으로 해서 시간초과가 나왔다. 굉장히 사소한 부분이라고 생각했는데, 테스트케이스를 많이 집어넣을 수 있는 방식이라서 시간초과가 난 것 같다. 그리고 main에 cin, cout 입출력 시간을 줄이기 위한 코드를 추가했더니 시간이 아주 조금 더 줄었다. 코드 #include #include #include using namespace std; #define MAX 10000 bool visited[MAX]; string BFS(int A, i..

문제 https://www.acmicpc.net/problem/1525 풀이 BFS를 이용해서 풀었다. 그리고 구조체를 만들어, 큐에 구조체를 넣는 방식으로 BFS를 구현했다. 첫 번째 시도 방문체크를 876543211 크기의 배열 이용 구조체 안에 int 3개(r, c, count), 3x3 vector 한 개 → 메모리 초과 ! 두 번째 시도 구조체에 너무 많은 것들이 들어있는게 문제인가 싶어서, 구조체안에 int 1개, string 1개만 넣도록 했다. → 메모리 초과 ! 최종 시도 방문 체크를 string set을 이용해서 했다. 876543211크기의 visited 배열을 만든 것 자체가 메모리 초과의 원인인 것 같았다. 코드 #include #include #include #include #i..

문제 https://www.acmicpc.net/problem/2146 각각의 섬(육지 덩어리?)에서 다른 섬 까지 갈 수 있는 모든 경우의 수 중에 최단 경로를 구하는 문제이다! 풀이 DFS와 BFS를 모두 이용했다. 먼저, 각 섬들의 번호를 구분하기 위해 DFS를 돌렸다. 그 후에 BFS를 돌려서 어떤 섬에서 또 다른 섬까지 갈 수 있는 모든 경우의 수를 구한 후에, 그 중에 최솟값을 출력했다. 맵의 크기(n)이 100이하이기 때문에 input이 작아서 시간초과 걱정 없이 풀었다. 코드 #include #include #include using namespace std; #define LAND 1 #define SEA 0 int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,..

문제 https://www.acmicpc.net/problem/2589 육지와 바다로 이루어진 nxm 맵에서 육지에서 시작해서, 바다를 거치지 않고 갈 수 있는 가장 먼 육지까지의 최단경로를 구하는 문제이다. 풀이 BFS를 이용해서 풀었다! 또한, 모든 육지가 시작점이 될 수 있기 때문에 완전탐색이기도 하다. 모든 육지에서 BFS를 돌려서, 다른 육지까지의 최단경로를 모두 구해서 그 중에 최댓값을 출력했다. 코드 #include #include using namespace std; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int map[52][52] = { 0, }; int cache[52][52] = { 0, }; int max_dist = 0; vo..

문제 www.acmicpc.net/problem/1707 풀이 처음에는, 벡터 두개를 만들어서 각 그룹에 노드들을 채워나가는 형식으로 했는데 문제점이 있었다. 그래프가 꼭 두 그룹으로 나뉘지 않는다는 것이었다. 아래 그림의 case2와 같이 독립적인 여러개의 그룹으로 나뉠 수 있었다. 그래서 얌전하게 일반적인 그래프 풀이 방식을 이용하였다. BFS로 그래프 탐색 후에, 해당 그래프가 이분그래프인지 확인하는 과정을 거쳤다. 간선을 입력받을 때, v1 -> v2만 저장해서 틀렸습니다가 나왔다. 무방향그래프이기 때문에, v2 -> v1도 저장해야한다! 그리고 BFS를 한 번만 돌리는 것이 아니라, 모든 노드를 방문할 때 까지 여러번 돌려야했다. 코드 #include #include #include using ..