[백준] #2206 G3 벽 부수고 이동하기_파이썬

벽 부수고 이동하기

🧐 아이디어

일단 4방향 탐색 사용해서 bfs로 탐색을 진행해야 한다는 것은 생각했는데, 벽을 부수는 것을 어떻게 확인할 건지를 떠올리는 로직이 어려웠다, 그래서 백트래킹을 써야하는 건가 등등 생각을 하다가 결국 검색을 진행함.

그 과정에서 2차원 배열이 아니라 방문 배열을 3차원 배열로 설계한다는 것을 알게되었다.

[i][j][k] : [행][열][0 or 1]
k가 0이면 벽을 뚫지 않고 간 경우, k가 1이면 벽을 뚫고 간 경우

이렇게 4방향 탐색을 진행하면서 해당 위치에 방문도 하지 않았고, 이동이 가능한 위치라면 방문값을 1늘려주고, q에 넣어주기
만약, 방문은 안 했지만 이동할 수가 없는 위치라면 아직 벽을 부수지는 않았다면 벽을 부쉈다는 의미로 k를 1로 바꿔주고 방문값을 1 늘려준다.

이 로직만 생각해낼 수 있었다면 기존의 bfs문제 유형과 차이는 없었다.

✏ 문제 풀이 코드

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


def bfs():
    q = deque()
    q.append((0, 0, 0))
    visited[0][0][0] = 1
    while q:
        i, j, k = q.popleft()
        if i == N - 1 and j == M - 1:
            return visited[i][j][k]
        for x in range(4):
            ni = i + di[x]
            nj = j + dj[x]
            if 0 <= ni < N and 0 <= nj < M:
                if visited[ni][nj][k] == 0 and graph[ni][nj] == 0:
                    visited[ni][nj][k] = visited[i][j][k] + 1
                    q.append((ni, nj, k))
                elif visited[ni][nj][k] == 0 and graph[ni][nj] == 1 and k == 0:
                    visited[ni][nj][k + 1] = visited[i][j][k] + 1
                    q.append((ni, nj, k + 1))
    return -1


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]

ans = bfs()
print(ans)

🗯 생각할 것

첫 풀이에서 시간을 땡겨보기 위해서 sys.stdin.readline을 사용했지만, 큰 변화는 없었던 것으로 봐서는 heapq를 활용해서도 한 번 풀어봐야겠다.