백준 16946 / BFS, 플러드 필 알고리즘(Flood Fill) / JAVA

오늘 설명할 문제는 백준 16946번 <벽 부수고 이동하기 4> 문제이다.

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

단순한 BFS 문제로 접근했다가 여러번 틀리고 깨달음을 얻은 문제이다. 처음에는 N * M 격자점들에 대해서 하나하나 BFS로 돌면서 이동할 수 있는 칸의 갯수를 세는 접근을 하였는데, 그렇게 하니 시간 초과가 나왔다.

그래서 이 문제에서 사용한 알고리즘은 플러드 필 알고리즘이다. 플러드 필 알고리즘은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 주로 색칠하는 문제에서 많이 사용된다. 어떤 칸에서 시작해서 해당 색깔에 해당되는 칸들을 모두 탐색한 다음 대체 색으로 바꾸어 주는 식으로 말이다. BFS와 DFS 둘 다 사용하서 구현이 가능한 알고리즘이다.

나는 BFS를 사용했다. 예제 2를 가지고 설명을 하면, 문제에서 주어진 맵에서 1은 벽이고 0은 이동할 수 있는 곳이다. 나는 해당 맵을 walls라는 boolean 타입의 이차원 배열으로 정의하고 벽이 있으면 true, 벽이 없으면 false를 입력했다.

그리고 나서 왼쪽 위에서 부터 이동할 수 있는 공간을 폴리드 필 알고리즘을 이용하여 그룹화 하는 작업을 진행했다. 한 번에 이동할 수 있는 영역을 인덱스 1으로 그룹화 하고, 그 다음 한 번에 이동할 수 있는 영역을 인덱스 2로 그룹화 하는 식으로 말이다. 이 때 BFS를 사용하였다. 위의 예제에서는 인덱스 6까지 그룹이 나오게 되었다. 나는 이 값들을 groups라는 int형 2차원 배열에 넣었다.

그리고 나서 walls를 하나씩 돌면서 이동할 수 있는 칸의 갯수를 세 주었다. 이 때 매번 BFS로 돌 필요가 없다. 왜냐하면 이전에 플러드 필 알고리즘을 통해서 각 groups을 만들었고 우리는 인덱스 값만 알면 몇 칸을 이동할 수 있는지 알 수 있기 때문이다.

첫 번째 칸의 경우 벽이 있기 때문에 부시고 이동을 할 수 있으며, 인접한 칸에 인덱스가 2만 있으므로 인덱스 2에 해당되는 값만 계산해 주면 된다. 그래서 첫 번째 칸은 3이 들어간다.

두 번째 칸의 경우 역시 벽이 있다. 인접한 칸에는 인덱스 1, 2가 있으므로 인덱스 1,2에 해당되는 값들을 더해주면 된다. 2+3이므로 두 번째 칸에는 5가 들어간다. 이런식으로 연산을 반복하면 모든 맵에 이동 가능한 칸 수를 파악하는데 N*M 의 시간만 소요가 된다.

맞긴 맞았지만, 좀 더 빠르게 푸는 방법을 고민해 보면 좋을 것 같다.

자바 소스 코드는 다음과 같다.