[백준] 2206. 벽 부수고 이동하기/Python - Gold 3

❓문제

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

성능 요약

메모리: 323464 KB, 시간: 1936 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

 

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

✍🏻풀이

이동하면서 벽을 한 개는 부술 수 있다고 한다. 그러면 우리는 벽을 부쉈는지 안 부쉈는지를 기록해야 한다. 그래서 나는 처음에 이동할 때 벽을 부쉈는지 안 부쉈는지에 대해 큐에만 기록하여 틀렸다.

우리는 이동할 때 벽을 부수고 갈 수도 있고 부수고 가지 않을 수도 있다. 그러므로 부수고 가는 경우와 부수지 않고 가는 경우를 나눠서 visited 배열을 3차원 배열로 하여 기록했다. visited[y][x][0]은 벽을 부수고 가지 않고 이동한 횟수를 나타내고, visited[y][x][1]은 부수고 이동한 횟수를 나타낸다.

만약 다음 위치가 1이고 아직 부순 적이 없다면 visted[ny][nx][1] = visited[cy][cx][0] + 1을 하여 기록한다. 그렇지 않고 다음 위치가 0이고 아직 방문한 적 없는 곳이라면 visited[ny][nx][crack] = visited[cy][cx][crack] + 1을 하여 기록하면 된다. 여기서 crack은 벽을 부쉈는지 부수지 않았는지를 의미한다.

이 같은 방법으로 기록을 하여 현재 위치가 (N-1, M-1)이라면 visited[N-1][M-1][crack]을 반환하면 되고, 그렇지 않다면 -1을 반환하면 된다.

💻코드

틀린 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(input().strip()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs():
    q = deque()
    q.append((0, 0, False))
    visited[0][0] = True
    cnt = 0

    while q:
        ln = len(q)
        for _ in range(ln):
            cy, cx, crack = q.popleft()

            if (cy, cx) == (N-1, M-1):
                print(cnt + 1)
                return

            for i in range(4):
                ny, nx = cy + dy[i], cx + dx[i]

                if 0 <= ny < N and 0 <= nx < M:
                    if not visited[ny][nx] and graph[ny][nx] == "0":
                        visited[ny][nx] = True
                        q.append((ny, nx, crack))

                    if graph[ny][nx] == "1" and not crack:
                        q.append((ny, nx, True))

        cnt += 1

    print(-1)

bfs()

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs():
    q = deque()
    q.append((0, 0, 0))
    visited[0][0][0] = 1

    while q:
        cy, cx, crack = q.popleft()

        if (cy, cx) == (N-1, M-1):
            return visited[cy][cx][crack]

        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]

            if 0 <= ny < N and 0 <= nx < M:
                if not visited[ny][nx][crack] and graph[ny][nx] == "0":
                    visited[ny][nx][crack] = visited[cy][cx][crack] + 1
                    q.append((ny, nx, crack))

                if graph[ny][nx] == "1" and crack == 0:
                    visited[ny][nx][1] = visited[cy][cx][0] + 1
                    q.append((ny, nx, 1))

    return -1

print(bfs())

📍후기

처음에는 그냥 큐에만 부쉈는지 안 부쉈는지 기록하면 된다고 생각했다. 그런데 생각해보니 도달하는 위치를 벽을 부수고 도달했을 수도 있고 그렇지 않을 수도 있다는 것을 깨달았다. 문제를 풀 때 너무 단순하게 생각하지 말아야 겠다.

그리고 평소에 변수를 따로 만들어서 이동 횟수를 기록하려고 했는데 생각해보니 visited에 저장해도 됐다. 괜히 변수 하나 더 만들어서 메모리를 늘리지 않도록 해야지...