[Python] 백준 2206번: 벽 부수고 이동하기

문제

2206번: 벽 부수고 이동하기

풀이

일단 2차원 배열문제는 bfs로 하는게 낫다는 말에 bfs로 시도! 

bfs로 탐색을 하면서 가는건 미로문제랑 유사하지만, 벽을 1번 뚫을수 있다는 조건이 붙어서 조금 어려웠다.

 

처음에는 visited배열을 안쓰고 인풋으로 받은 field 배열에 방문한곳의 값을 바꿔줬었는데

주어진 테스트케이스는 다 통과하지만 틀렸습니다가 나오는 문제가 있었다.

 

생각해보니 

0	0	0	0
0	1	0	0
0	0	0	0
1	1	1	1
0	0	0	0

이런 경우에

노란색으로 표시된 곳에 벽을 뚫지 않고도 충분히 올 수 있는 곳임에도 불구하고 

1을 부수고 온 애가 먼저 도착할 경우, 밑에 초록색 1111 줄을 뚫지 못하게된다. 

 

즉 벽을 부숴서 들어온애가 먼저 접근해버리면 안부수고도 같은 자리에 올 수 있는데

그걸 못하게되기 때문에 맵을 두개 쓰는 방식으로 바꿨다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split(" "))
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

# 방문 확인용 배열
visited = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(2)]
# 인풋으로 받을 배열
field = []

for _ in range(N):
    field.append(list(map(int, sys.stdin.readline().strip())))

queue = deque()

# 시작점이 완료점일 경우
if N == 1 and M == 1 and field[0][0] == 0:
    print(1)
else:
    visited[0][0][0] = 1
    queue.append([0, 0, 0])

    flag = 0
    while queue:
        x, y, z = queue.popleft()

        for i in range(4):
            ndr = x + dr[i]
            ndc = y + dc[i]

            # 범위안에 들어옴
            if 0 <= ndr < N and 0 <= ndc < M and visited[z][ndr][ndc] == 0:

                c = 0
                # 벽을 만났는데 아직 벽을 안뚫어봄
                if field[ndr][ndc] == 1 and z == 0:
                    visited[1][ndr][ndc] = visited[0][x][y] + 1
                    queue.append([ndr, ndc, 1])
                    c = 1
				
                # 벽 안만남 (길을 만난 경우)
                elif field[ndr][ndc] == 0:
                    visited[z][ndr][ndc] = visited[z][x][y] + 1
                    queue.append([ndr, ndc, z])

                # 도착한 경우
                if ndr == N-1 and ndc == M-1:
                    print(visited[z][ndr][ndc])
                    flag = 1
                    break

        if flag == 1:
            break

    if flag == 0:
        print(-1)

99퍼센트에서 틀렸습니다가 나길래 반례를 엄청 찾아봤는데

 

1 1

0

(답: 1)

 

즉 시작점이 도착점인 경우를 처리 안해줬었다.