[Python] 3140번 GULIVER

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

---

 

25/09/03

 

 

재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다.

---

 

문제 접근 방식:

 

 

두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값을 묻는 문제이다.

 

처음에 생각했던 방법은 왼쪽에서 오른쪽으로 순회하면서 진행하는 2차원 DP였다.

 

$DP[r][c]$ $=$ $r$행 $c$열까지 봤을 때 두 조각으로 분리하기 위해 필요한 벽의 개수의 최솟값 으로 DP식을 정의하고 돌렸다.

 

당연히 틀렸다.

 

틀린 후에는 태그를 까고 0-1 BFS라는 사실을 알게된 후에, 벽일 때는 0의 코스트로 가고 벽이 아닐 때는 1의 코스트로 가서 왼쪽에서 오른쪽으로 순회하도록 짰다.

 

근데 틀렸다. 진행방향을 오른쪽 위, 오른쪽, 오른쪽 아래로만 잡아서 그렇기 때문인데, 반례는 다음과 같다.

 

......
...###
..#...
......
#..#..
.##...

 

이 예시는 가운데에 벽 하나만 놓으면 분리되는 예시인데, 이렇듯 오른쪽으로만 진행하면 온전하게 찾을 수 없다.

 

따라서 BFS를 진행하되, 오른쪽만 보는 것이 아니라 8방향 다 볼 수 있도록 진행하면 최솟값을 찾을 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3140번 GULIVER
# 0-1 BFS
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
MAP = [list(input().rstrip()) for _ in range(N)]
dr, dc = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
queue = deque()
visited = [[-1 for _ in range(M)]
           for _ in range(N)]
for r in range(N):
    if MAP[r][0] == '.':
        visited[r][0] = 1
        queue.append((r, 0))
    else:
        visited[r][0] = 0
        queue.appendleft((r, 0))
while queue:
    r, c = queue.popleft()
    if c == M-1:
        print(visited[r][c])
        break
    for i in range(8):
        nr, nc = r+dr[i], c+dc[i]
        if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == -1:
            if MAP[nr][nc] == '.':
                visited[nr][nc] = visited[r][c] + 1
                queue.append((nr, nc))
            else:
                visited[nr][nc] = visited[r][c]
                queue.appendleft((nr, nc))