파이썬 백준 2206번 : 벽 부수고 이동하기

문제 

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

 

 

풀이

최단경로이므로 BFS를 이용했다.

visited는 set자료구조를 사용하여 (행,열,벽을 부순경우)로 저장했다.

import sys
from collections import deque
n,m=map(int,sys.stdin.readline().split())
maps=[]
answer=-1
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for _ in range(n):
    maps.append(list(map(int,sys.stdin.readline().strip())))
visited=set()
queue = deque()
queue.append((0, 0, 0, 0))
while queue:  # 큐가 빌때까지 반복
    x, y, is_break, cnt = queue.popleft()
    if x >= n or x < 0 or y >= m or y < 0 :
        continue
    if x == n - 1 and y == m - 1:  # 끝에 도달
        answer = cnt+1
        break
    cnt += 1
    for j in range(4):  # 사방탐색(queue append)
        nx=x + dx[j]
        ny= y + dy[j]
        if n > nx >= 0 and m > ny >= 0:
            if maps[nx][ny]!= 0 :  # 벽인 경우
                if is_break==0 and (nx,ny,1) not in visited: #벽을 부술수 있는 경우
                    queue.append((nx, ny, is_break+1, cnt))
                    visited.add((nx, ny, is_break+1))  # 방문처리
            elif (nx,ny,is_break) not in visited: #벽이 아닌경우
                queue.append((nx, ny, is_break, cnt))
                visited.add((nx, ny, is_break))  # 방문처리

print(answer)

 

 

😎덧) 

무조건 방문을 찍고 넘어가는게 아니라 벽을 부쉈는지 여부에 따라 visited를 업데이트 해야한다.

예를 들어, (0,0)->(2,0)으로 간경우 이후의 벽을 부술 수 없다. (0,0) -> (1,0) -> (2,0) 인경우 이후의 벽을 부술수 있다!

처음에 18%정도에서 틀려서 발견했다.. 

#반례
6 5 
00000
11110
00000
01111
01111
00010 

#정답 18