🪴 Quartz 4.0

BOJ 2206 - 벽 부수고 이동하기

2 min read

풀이

처음에는 3차원배열로 방문처리를 받지 않고 주어진 2차원배열에서 값을 수정해주는 식으로 방문처리를 대체했고 큐에 들어가는 요소들에만 벽을 뚫을 수 있는지의 여부를 함께 삽입했다.

테스트 케이스에서는 모두 통과했지만 자꾸 틀린 답이 나왔다길래 다른분들의 코드를 참고했다.

아이디어는 같지만 내 코드와 다른점은 3차원 배열로 따로 방문처리를 해줬다는 것이다.

굳이 왜 저렇게 해야하는지 아직까지 의문이라 조금 더 공부해봐야겠다.

소스코드

# 벽 부수고 이동하기
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(i, j):
    q = deque()
    q.append([i, j, 1])
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visited[i][j][1] = 1  # 시작 점 방문처리
    while q:
        x, y, penetrate = q.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][penetrate]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m:  # 범위 내 일 때
                if board[nx][ny] == 1 and penetrate == 1:
                    visited[nx][ny][0] = visited[x][y][1] + 1  # 방문 처리
                    q.append([nx, ny, 0])
                elif board[nx][ny] == 0 and visited[nx][ny][penetrate] == 0:
                    visited[nx][ny][penetrate] = visited[x][y][penetrate] + 1  # 방문 처리
                    q.append([nx, ny, penetrate])
    return -1
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
 
print(bfs(0, 0))

References

Graph View