[백준 2665][파이썬] 미로 만들기

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

2665번: 미로만들기

 

흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력하는 문제이다.

 

그래프로 탐색을 하면서 특정 좌표에 도착하기까지 바꿔야 할 검은 방의 최소값을 갱신해가면 된다.

 

흰 방부터 생각해보자.

 

첫 번째 좌표인 (0, 0)에서는 바꿔야 할 검은 방의 개수가 0이다.

 

또한 이 첫 번째 좌표와 연결된 모든 흰 방의 좌표 역시 바꿔야 할 최소 검은 방의 개수가 0이다.

 

당연하게도 연결되어 있는 모든 흰 방의 좌표의 바꿔야 할 최소 검은 방의 개수가 동일할 것이다.

 

그렇다면 검은 방의 경우는 어떨까?

 

검은 방의 경우 연결되어 있는 모든 검은 방의 좌표의 바꿔야 할 최소 검은 방의 개수가 동일할 수도 있지만 그렇지 않은 경우가 더 많을 것이다.

 

한 번 위 그림에서 4x4만 떼어내서 각 좌표마다 바꿔야할 최소 검은 방의 개수를 알아보자.

 

bfs를 사용해서 탐색을 진행할 때 "흰 방에 도착했을 때"와 "검은 방에 도착했을 때"의 차이를 확인해보자.

 

흰 방에 도착했을 때는 다음과 같다. (일부만 표시)

흰 방에서 흰 방으로 도착할 때와 검은 방에서 흰 방으로 도착할 때 모두 "이전 값과 동일"하다는 것을 알 수 있다.

 

검은 방에 도착했을 때는 다음과 같다. (일부만 표시)

흰 방에서 검은 방으로 도착할 때와 검은 방에서 검은 방으로 도착할 때 모두 "이전 값보다 1 큰 값"이라는 것을 알 수 있다.

 

결론적으로 흰 방에 도착할 때는 이전 값과 동일한 값, 검은 방에 도착할 때는 이전 값보다 1 큰 값을 저장하면 된다.

 

또한 최단 거리를 구하는 문제나 마찬가지이기 때문에 bfs를 사용하면 된다.

 

보통 bfs를 통해 최단 거리를 해결할 때 방문 여부를 체크해서 방문하지 않은 노드만 방문하도록 코드를 작성한다.

 

그런데 이 문제는 이렇게 하면 해결할 수 없다.

 

예를 들어 다음과 같은 상황에서 동남서북 방향으로 bfs를 진행하고 방문하지 않은 노드만 방문한다고 해보자.

그러면 아래와 같이 진행될 것이다.

실제로는 왼쪽 하단에 있는 검은 방만 바꾸면 되기 때문에 정답은 1이 되어야 하지만 방문한 노드는 방문하지 않았기 때문에 4라는 결과가 나왔다.

 

즉 방문한 노드를 재방문해서 최소값을 계속 갱신해나가야 하는 문제이다.

 

위에서는 검은 방에 도착할 때를 예시로 들었는데 잘 생각해보면 흰 방에 도착할 때도 재방문하여 최소 값을 갱신해가야 한다.

 

재방문하는 조건은 흰 방의 경우 이번 방문하는 노드의 값이 이전 값보다 작을 때이고 검은 방의 경우 이번 방문하는 노드의 값이 이전 방문하는 노드의 값에 1을 더한 값보다 작을 때이다.

 

<최종 코드>

import sys
from collections import deque
dx = [0, 0, 1, -1] # 동서남북
dy = [1, -1, 0, 0] # 동서남북
input = sys.stdin.readline
n = int(input())
arr = [list(input().rstrip()) for _ in range(n)]
cnt = [[1e9]*n for _ in range(n)] # 흰 방으로 바꾼 횟수
queue = deque()
queue.append((0, 0))
cnt[0][0]=0
while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<n and 0<=ny<n:
            if arr[nx][ny]=='1' and cnt[nx][ny] > cnt[x][y]:
                cnt[nx][ny] = cnt[x][y]
                queue.append((nx, ny))
            elif arr[nx][ny]=='0' and cnt[nx][ny] > cnt[x][y]: 
                cnt[nx][ny] = cnt[x][y]+1
                queue.append((nx, ny))

print(cnt[n-1][n-1])