[백준]2206(파이썬) - 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

• 이 문제는 푸는데 정말 오래 걸린 문제입니다. 푸는 방법까지는 생각했는데 구현이 정답률 33프로 이상으로는 넘어가지 못했던 문제죠.
• 이 문제의 핵심은 벽을 한 번 부수고 이동할 때 어떻게 체크를 할 것인가? 입니다. 처음에 풀 때는 flag를 0,1 로 나눠서 1이 처음 나왔을 때 flag를 1로 바꿔주고 bfs로 구현을 했는데요, 이렇게 됐을 경우 아래와 같은 테스트 케이스를 통과할 수 없다는 점을 찾아냈습니다.
  00000
  01 000
  0 0000
  1 1 1 1 1
  00000
  위와 같은 테스트 케이스가 주어지면 가운데 있는 1을 사용하지않고 최단거리를 구할 수 있지만 만나면 사용하게 되고, flag가 1이 되어 버렸으니 아래 1만 있는 4번째 줄을 통과 할 수 없게 되죠.
• 그래서 생각한 방식이 같은 칸을 가더라도 벽을 부술 수 있는 기회 한 번을 사용했는지, 사용하지 않았는지를 확인해 줘야겠다! 였습니다. 결론적으로는 3차원 배열을 생각했고, 같은 칸을 갈 때 기회를 사용했으면 (x,y,1) 을 넣어주고, 사용하지 않았다면 (x,y,0) 을 넣어줘서 bfs로 구현했습니다.
• 3차원 배열을 생각하기까지는 꽤 많은 시간이 걸렸지만 한 번 풀어보니 어떤 경우에 3차원 배열이 효율적인지를 알 수 있었던 문제였습니다. 
• 주석 처리 한 부분은 제가 처음에 풀었던 풀이입니다.

 

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())
graph  = []
for _ in range(n):
    graph.append(list(input().rstrip()))
# print(graph)

dx = [0,1,0,-1]
dy = [1,0,-1,0]
cnt = [[0]* m for _ in range(n)]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
def bfs():
    q = deque()
    q.append((0,0,0))
    visited[0][0][0] = 1
    while q:
        x,y,wall = q.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][wall]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][wall] == 0:
                if graph[nx][ny] == '0':
                    q.append((nx,ny,wall))
                    visited[nx][ny][wall] = visited[x][y][wall] + 1
                if wall == 0 and graph[nx][ny] == '1':
                    q.append((nx,ny,1))
                    visited[nx][ny][1] = visited[x][y][wall] + 1
        print(q)

                #  if wall == '0':
                #     q.append((graph[nx][ny],nx,ny))
                #     cnt[nx][ny] = cnt[x][y] + 1
                #     visited[nx][ny] = 1
                #  elif  wall == '1' and graph[nx][ny] == '0' and flag == 0:
                #     cnt[nx][ny] = cnt[x][y] + 1
                #     visited[nx][ny] = 1
                #     q.append(('0',nx,ny))
                #     flag = 1
        # print(q)
    return -1

# print(visited)
# print(cnt)
# if visited[n-1][m-1] == 0:
#     print(-1)
# else:
#     print(cnt[n-1][m-1])
print(bfs())