챕터6-5. 그래프 | 문제풀이(2) - 플러드필 알고리즘(DFS, BFS 탐색응용)

플러드필 알고리즘

- 어떤 배열을 채우는 알고리즘이며, 어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다.
- dx, dy 가 사용됨.

유형1. 동시에 진행되는 탐색이 1개뿐인 것

# 단지에 번호를 붙이는 문제
- https://www.acmicpc.net/problem/2667
- 문제요약 :
   정사각형 모양의 지도가 주어지는데, 0은 집이 없는 곳이고 1은 집이 있는 곳이다.
   이 때 지도를 보고, 연결된 집의 모임 각각에 번호를 붙이려고 한다. 
   현재 위치를 기준으로 좌, 우, 아래, 위 중 한 곳이라도 집이 있다면 연결되었다고 할 수 있다.
- 이 문제는 (x, y)형태로 값이 주어지지만, 이 값들을 그래프로 보면 연결요소의 개수를 구하는 것과 같다.
   BFS 혹은 DFS를 이용해서 탐색을 수행하는 것을 통해 해결할 수 있는 문제이다.

- check[i][j] = "(i, j)를 방문 안했다면 0, 방문 했다면 단지번호"를 이용해 해결할 수 있음.
- 인접행렬이나 인접리스트를 만들 필요는 없다. 그 이유는
   간선으로 연결된 정점은 좌, 위, 우, 아래 중 한 칸이기 때문에 모든 칸 마다 4개의 칸을 검사하면 되기 때문이다.

- 모든 땅에 번호를 매기는 것을 완료하였다면, 그 번호들을 각각 카운트 해준다.
   이는 ans[땅에 매겨진번호] += 1을 함으로써 수행할 수 있다.

* 자주 실수하는 부분
- dx, dy는 동시에 같은 인덱스만 뽑아써야 한다는 것을 상기해두자.
- ans 배열에서 맨 앞의 0은 사용하지 않았으므로 sort(ans+1, ans+cnt+1) 처럼 +1 해주는 것을 잊으면 안된다.
- DFS, BFS 두려워하지 마라.
   check배열을 사용해 중복방문은 하지않으며, 간선이 있으면 가는거고 아니면 안가는 거라고 간단히 생각하자.

# 섬의 개수를 구하는 문제
- https://www.acmicpc.net/problem/4963
- 바로 위의 문제와 비슷한 문제인데, 차이점은 연결의 범위가 대각선 방향도 포함된다는 것이다. 
   이것은 아래와 같이 방향을 4개 더 추가해줌으로써 해결이 가능해진다.
- 주의할 점은 이중 for문 사용할 때 i는 h이고, j는 w이라는 점이다.

# 미로탐색, (1, 1) 에서 (N, M)으로 가는 가장 빠른 거리를 구하는 문제
- https://www.acmicpc.net/problem/2178
- 가장 빠른 길을 구하는(최단경로) 문제 이므로 BFS 탐색만 사용이 가능하다.
   BFS 탐색은 모든 가중치가 1이면 최단거리 경로를 찾을 수 있다.
- dist[i][j] = "방문여부 및 (1, 1)부터 (i, j)까지의 거리"
   dist[next] = dist[now] + 1 이 방식으로 모든 탐색가능한 정점에 거리를 구해주면 최단거리를 구할 수 있음.
   BFS탐색으로 모든 점에 대한 dist를 구한 뒤 dist[m-1][n-1]를 출력해주면됨.

유형2. 동시에 진행되는 탐색이 2개이상인 것

# 토마토
- https://www.acmicpc.net/problem/7576
- 미로탐색 문제와 똑같은 방식으로 풀면 되지만, 이 문제는 탐색이 여러군데서 동시에 단계적으로 진행된다는 다른 특징을 가진다.
- 시작점이 여러개이고, 그 점들에 대해서 동시에 BFS를 진행시켜야 한다면, 그 시작점들을 모두 큐에 넣고 탐색을 시작하면 된다.
- 사용되는 변수를 줄이고 싶다면 dist 배열을 -1로 초기화 하여 방문하지 않은 경우를 -1로 표시해주고,
   0이상이면 방문했고 익은 토마토로부터의 거리를 의미하도록한다.

시작점이 1개인 경우

시작점이 2개인 경우

# 여러 섬으로 이루어진 나라에서 두 섬을 연결하는 가장 짧은 다리를 찾는 문제
- https://www.acmicpc.net/problem/2146
@ 방법1(느림)
- 단지번호붙이기 + 토마토 문제 처럼 먼저 섬을 그룹으로 나누어 group[i][j] = (i, j)의 그룹번호를 매긴다.
- 그 다음 각각의 그룹에 대해서 BFS탐색을 이용해 모든 땅에대한 거리를 계산한다.
   이 때 해당 그룹에서 다른 땅까지의 최단거리는 그룹번호가 다른 곳의 거리값을 보면 된다. 그중 가장 작은 값을 선택.
- 이 방법은 각각의 그룹에 대해서 BFS 알고리즘을 수행해야 하기 때문에 느리다.

그룹번호를 매긴것

@ 방법2(빠름)
- 이 방식은 위의 방식과 다르게 각 그룹마다 dist를 구하기 위해 했던 작업이 없어진다.
- 단지번호붙이기 + 토마토 문제 처럼 먼저 섬을 그룹으로 나누어 g[i][j] = (i, j)의 그룹번호를 매긴다.
- 그룹번호와 거리 두가지를 각각 BFS 탐색으로 확장시킨다.
- 확장시킨 배열에서 인접한 칸인데, 다른 그룹번호를 가진다면 이는 다리가 놓일 수 있는 위치이며, 
   다리의 길이는 인접한 두 칸이 가진 dist값을 합한 값임.
   이 값들 중 가장 작은 값을 찾으면 됨.