[백준] 그래프 탐색 - BFS (골드4~5) 코멘트 모음

알고리즘 문제 중 그래프 탐색 문제, 그 중에서도 BFS 문제 풀이를 가장 좋아한다.

 

그래서 그런지 골드 문제 풀이 비중도 BFS가 가장 높고,

나중에는 연속 문제풀이를 유지하기 위해 그래프 문제를 빠르게 해치웠었다.

 

DFS로 풀 수 있는 문제도 항상 BFS로 풀어서 코멘트를 남긴 문제가 꽤 많기 때문에,

골드4~5와 골드1~3으로 나눠서 정리해보겠다.

 

🙋🏻 BFS를 사용하는 이유

최소거리, 최소시간 등을 구해야하는 문제에 사용한다.

 

Queue를 사용하여 구현하기 때문에 항상 거리(시간)이 똑같은 케이스들이 먼저 나온다는 점이 핵심이다.

 

이러한 특징 때문에 조건에 맞는 첫 케이스가 항상 최소 거리(시간)임을 확정할 수 있어 사용한다.

 

 

⭕️ 7576번 : 토마토 (골드5)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 하루마다 익은 토마토별로 인접한 한 칸씩 익기 때문에 bfs 탐색을 이용
- 모든 토마토가 익는 시간을 정확히 재기 위해선 하루마다 익은 토마토와 인접한 토마토만 익어야 되기 때문에 반복할 때마다 큐의 사이즈만큼만 토마토를 빼내어 bfs 탐색을 진행해야 함
- 더 이상 익을 수 있는 토마토가 없을 때 (큐가 비었을 때) 총 토마토의 개수와 익은 토마토의 개수를 비교하여 모든 토마토가 익을 수 있는지

 

⭕️ 7569번 : 토마토 (골드5)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 7576번 토마토에서 상자가 수직으로 쌓아 올려지는 형태로 4방향 탐색이 아닌 위, 아래를 포함한 6방향 탐색 진행

 

⭕️ 10026번 : 적록색약 (골드5)

• 문제 유형 : graphs, bfs, dfs
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 서로 같은 색깔이면서 이어져있는 구역의 개수를 정상인의 시선과 적록색약의 시선의 경우를 각각 구해야하기 때문에 dfs와 bfs 모두 가능
- 정상인 시선의 경우 아직 방문하지 않은 노드를 시작 색깔로 하고 일반적인 bfs 탐색을 해서 구역의 개수를 구함
- 적록색약 시선의 경우 동일하게 아직 방문하지 않은 노드를 시작 색깔로 하고 bfs 탐색을 하지만 시작 색깔이 빨간색 혹은 초록색일 경우 서로 색깔 구분을 하지 않고 탐색해서 구역의 개수를 구함

 

⭕️ 2589번 : 보물섬 (골드5)

• 문제 유형 : graphs, bfs, bruteforce
• 시간 복잡도 : O(n^2m^2)
• 풀이 방식 :

- *알고리즘 분류 안보고 브루트포스인거 모르고 시작했으면 시간 좀 걸렸을 듯(케이스의 범위가 작음, 메모리 제한이 큼)
- *그래프 내의 한 집합에서 bfs탐색을 이용해 가장 멀리 떨어진 두 노드를 알고 싶으면 브루트포스를 이용해야 하는 듯
- 2중 for문을 이용해서 graph를 순회하면서 육지 노드를 만날 때마다 bfs탐색 시행
- bfs 탐색 시작 전에 방문 체크를 하는 visit 배열을 초기화하며 시작 노드와 큐에서 빼낸 노드 사이의 거리가 기존에 구해놨던 가장 먼 거리보다 길면 저장

 

❌ 14502번 : 연구소 (골드4)

• 문제 유형 : graphs, bfs, dfs, implementation, simulation, bruteforce
• 시간 복잡도 : O((nm)^3)
• 풀이 방식 :

- 바이러스를 인접한 4방향으로 계속해서 퍼트린 후 안전 영역을 구하면 되기 때문에 dfs, bfs 모두 가능
- 벡트레킹을 이용해서 벽 3개를 세울 수 있는 모든 경우에서 바이러스를 시작점으로 bfs 탐색을 진행
- 벽 3개가 세워진 각 경우마다 시뮬레이션을 각각 진행해야 되기 때문에 연구소 지도를 복사해서 사용
- 바이러스가 퍼질때마다 안전 영역의 크기를 줄이면서 가장 큰 안전 영역의 크기를 구함

 

❌ 17141번 : 연구소 2 (골드4)

• 문제 유형 : graphs, bfs, implementation, simulation, bruteforce
• 시간 복잡도 : O(10Cm∗n^2*M)
• 풀이 방식 :

- 바이러스를 놓을 수 있는 위치를 리스트에 저장
- 바이러스는 1개부터 m개 모두 놓기까지 모든 경우의 수가 가능하며 각 경우마다 벡트레킹을 이용해서 바이러스를 나열하고 모든 바이러스를 놓았으면 bfs 탐색을 진행하여 바이러스를 퍼트림(bfs 탐색은 그래프의 복사본에서 진행)
- bfs 탐색의 한 사이클은 큐의 사이즈 크기만큼 진행되며(각 시간마다 모든 바이러스의 퍼짐), 사이클마다 큐의 사이즈를 더하여 바이러스가 퍼질 수 있는 구역의 수와 같으면(바이러스가 벽을 제외한 모든 곳에 퍼질 수 있으면) 현재까지 구한 최소 시간과 비교
- *연구소(14502번)을 푼지 오래되서 각 bfs 탐색마다 그래프를 복사해서 따로 사용해야되는 것을 잊음

 

⭕️ 16509번 : 장군 (골드5)

• 문제 유형 : graphs, bfs, implementation, simulation, bruteforce
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 상은 이동할 때 전진, 대각선, 대각선의 방식으로 8방향으로 이동하게 되며 이동 중에 다른 말이 있을 경우 해당 방향으로는 이동하지 못함(해당 문제의 경우 다른 말은 왕만 존재)
- 앞선 두 번의 이동 중에 장기판 밖으로 나가거나 경로가 왕의 위치와 겹치게 되면 해당 방향으론 이동하지 않고, 마지막 대각선 이동에서는 이동 위치가 이미 방문한 곳이거나 장기판 범위를 벗어나는 경우를 제외한 위치를 큐에 집어넣으며 bfs 탐색
- 큐에서 빼낸 노드가 왕의 위치와 동일하면 해당 노드에 저장되어 있는 이동 횟수를

 

⭕️ 4179번 : 불! (골드4)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 세준이가 미로를 통과하는 가장 빠른 탈출 시간을 구해야 하기 때문에 bfs를 이용
- 세준이와 불의 속도가 같기 때문에 방문 체크를 하는 visit배열을 공유해서 사용해도 됨 (이미 세준이가 지나간 경로에 번지는 불은 세준이의 이후 경로에 영향을 끼치지 못하기 때문에)
- 불과 세준이의 bfs 탐색을 따로 진행해야하기 때문에 두 개의 큐를 사용하며, 시간 당 불과 세준이는 4방향으로 1칸씩 움직일 수 있기 때문에 반복 할 때마다 각각의 큐 사이즈만큼씩만 노드를 빼내어 bfs 탐색 진행
- 불과 세준이가 동시에 만나는 경로는 갈 수 없는 경로이기 때문에 무조건 불의 bfs 탐색을 먼저 진행
- 위의 과정을 세준이의 경로를 저장하는 큐가 빌 때까지(세준이가 더 이상 이동하지 못할 때까지) 반복
- 세준이가 미로의 가장자리에 처음 도달 했을 때가 가장 빠른 탈출 시간이기 때문에 반복문 즉시 종료

 

⭕️ 14923번 : 미로 탈출 (골드4)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(nm*2)
• 풀이 방식 :

- 2206번 벽 부수고 이동하기 풀이와 동일

 

⭕️ 15971번 : 두 로봇 (골드4)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(e)
• 풀이 방식 :

- 두 로봇이 통신 하기 위해 최소로 이동하기 위해서는 경로 상의 통로중 가장 긴 통로를 두 로봇 사이에 끼고 통신을 해야함
- 즉, 두 로봇이 위치한 노드 사이의 간선(통로) 중 가장 큰 가중치(길이가 가장 긴) 간선을 알아내어 총 길이에서 빼내면 됨
- 모든 간선 정보는 인접 리스트에 저장
- 간선이 노드 개수 - 1개인 트리 형태의 그래프로 사이클은 존재하지 않으며, 양방향 그래프이기 때문에 이미 지나온 길로 되돌아가지 않도록 방문 체크용 visit배열을 이용
- 왼쪽 로봇이 위치한 노드부터 큐에 들어가는 노드 정보에 지나온 간선 중 가장 큰 가중치 값을 포함하여 bfs탐색을 진행하며 오른쪽 로봇이 위치한 노드에 방문하게 되면 총 거리에서 가장 긴 통로의 길이를 빼내어 결과값에 저장하고 탐색 종료

 

⭕️ 3055번 : 탈출 (골드4)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 물이 침범 할 수 없는 목적지(비버의 굴)  하나가 존재한다는 점 외에는 4179번 불! 문제와 풀이방법이 동일

 

⭕️ 16234번 : 인구 이동 (골드5)

• 문제 유형 : graphs, bfs, implementation, simulation
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 그래프 내의 노드들 중 방문하지 않은 노드에서 bfs 탐색
- 현재 노드에서 4방향 탐색을 진행하여 인접한 노드와의 인구 격차가 L 이상 R 이하이면 해당 노드를 bfs queue와 연합 국가를 저장하는 queue에 넣고 인구값을 sum 변수에 더하고 연합 수를 의미하는 count 변수를 1 늘림
- 하나의 연합을 모두 탐색 했다면 모든 연합 국가의 인구수를 총 인구수 / 연합 국가 수로 바꿈
- 방문하지 않은 노드가 없을 때까지 bfs 탐색
- 인구 이동이 일어나지 않을 때까지 위의 과정을 반복

 

⭕️ 6593번 : 상범 빌딩 (골드5)

• 문제 유형 : graphs, bfs
• 시간 복잡도 : O(knm)
• 풀이 방식 :

- 시작점으로부터 도작점까지의 최소 시간을 구하는 것이기 때문에 bfs 탐색 이용
- 빌딩 즉, 3차원 배열에서 도착점을 찾아야하기 때문에 일반적인 4방향 탐색이 아닌 위 아래를 포함한 6방향 탐색을 하여 구함
- 큐가 빌 때까지 도착 지점에 도달하지 못할 경우 "Trapped!" 출력, 도달 했을 경우 양식에 맞게 최소 시간

 

❌ 1707번 : 이분 그래프 (골드4)

• 문제 유형 : graphs, bfs, dfs
• 시간 복잡도 : O(V+E)
• 풀이 방식 :

- 이분 탐색 그래프 : 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는 그래프 (그래프를 두가지 색으로 칠할 때 bfs 탐색의 측면에서 같은 레벨의 노드는 같은 색을 가져야 함)
- 간선의 정보를 인접 리스트에 저장
- 인접 리스트를 이용해서 그래프를 전체 탐색하기 때문에 bfs, dfs 모두 가능
- 방문 하지 않은 노드에 0 또는 1을 넣고, 인접한 노드들은 현재 노드와 반대되는 값을 넣으면서 bfs 탐색을 진행
- bfs 탐색 진행 중 현재 노드의 값과 인접한 노드의 값이 같은 경우가 발생하면 이분 그래프 조건을 만족하지 않는 것
- 무조건 모두 이어진 그래프가 아니기 때문에 방문하지 않은 노드를 찾아 위의 과정을 반복

 

⭕️ 2573번 : 빙산 (골드4)

• 문제 유형 : implementation, graph, dfs, bfs
• 시간 복잡도 : O(t*nm)
• 풀이 방식 :

- 2중 for문을 이용하여 빙산 노드를 탐색
- 탐색한 빙산 노드부터 시작하여 bfs 탐색을 시작
- 현재 노드의 주변 노드가 바다면 노드의 값과 전체 총 빙산 값을 -1 하고, 빙산이면 queue에 추가
- 현재 노드로부터 4방향 탐색이 끝났다면 현재 빙산 수치를 탐색한 빙산 총값을 의미하는 변수에 더한다
- bfs 탐색을 총 빙산 수치가 0이 될 때까지 진행하며 만약 queue가 비었을 때 탐색한 빙산 값과 남은 총 빙산 수치가 다르다면 빙산이 두 덩어리 이상 존재하는 것이기 때문에 반복문을 즉시 종료