[백준] 16946번 벽 부수고 이동하기4 (자바 풀이)

문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 처음에는 모든 벽에서 BFS를 돌려 모든 벽마다 갈 수 있는 곳을 세려고 했으나 이렇게 하면 시간초과가 난다 ㅠㅠ 그래서 다른 방법을 생각해냈다. 모든 0의 묶음을 개수로 표시하고, 해당 벽에서 4방향을 조사해서 다른 묶음이라면 0의 개수를 더해주기만 하면 된다. 예를 들어, 아래와 같은 상황이 있다고 하자. 010 1x2 110 -> xx2 (x는 벽, 숫자는 0..

원문링크 : [백준] 16946번 벽 부수고 이동하기4 (자바 풀이)