골드가 익숙해지지 않아.. (골드4)

#2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

굉장히 단순한 bfs문제라고 생각하고 풀었다.

 

틀린코드

from collections import deque

# 벽을 부술 수 있는지 여부를 boolean으로 전달하기.
# 상하좌우 이동
# 막히면 끝
# 최단경로 -> bfs
# 0,0 -> N,M

N, M = map(int, input().split())

maps = [[int(x) for x in input()] for _ in range(N)]
# print(maps)
visited = [[False]*M for _ in range(N)]

visited[0][0] = True
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]


def solve(x, y, crash, count):
    que = deque()
    que.append([x, y, crash, count])

    while que:
        x, y, crash, count = que.popleft()
        if x == N-1 and y == M-1:
            return count
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # print(nx, ny)
                visited[nx][ny] = True
                if maps[nx][ny] == 0:
                    que.append([nx, ny, crash, count+1])
                else:
                    if crash:
                        que.append([nx, ny, False, count+1])
                    else:
                        continue
    return -1


print(solve(0, 0, True, 1))

que에 새로운 좌표를 넣어줄 때 마다 벽을 부쉈는지의 여부를 더해서 올려줬었다. 하지만 틀림

뭐가 잘못된건지 ㄷ대체 모르겠어서 구글링을 했다,.

 

정답코드

from collections import deque

# 벽을 부술 수 있는지 여부를 boolean으로 전달하기.
# 상하좌우 이동
# 막히면 끝
# 최단경로 -> bfs
# 0,0 -> N,M

N, M = map(int, input().split())

maps = [[int(x) for x in input()] for _ in range(N)]
visited = [[[0, 0] for __ in range(M)] for _ in range(N)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]


def solve():
    que = deque()
    que.append([0, 0, 1])
    visited[0][0][1] = 1
    while que:
        x, y, w = que.popleft()
        if x == N-1 and y == M-1:
            return visited[x][y][w]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if maps[nx][ny] == 1 and w == 1:
                    visited[nx][ny][0] = visited[x][y][1] + 1
                    que.append([nx, ny, 0])
                elif maps[nx][ny] == 0 and visited[nx][ny][w] == 0:
                    visited[nx][ny][w] = visited[x][y][w] + 1
                    que.append([nx, ny, w])
    return -1


print(solve())

틀린코드의 문제점 중 하나는 최단거리일거란 보장이 없다는 점이다.

벽을 뚫은 경우와 뚫지 않은 경우가 visited라는 방문기록 리스트를 공유하기 때문이다.

따라서 각각의 경우를 분리해줄 필요가 있다.

하나의 노드에 도달했을 때, 벽을 뚫고 왔을 때의 거리(weight)와 벽을 뚫지 않고 왔을 때의 거리를 별도로 기록해줘야한다.

그렇게 할 경우에만 오류가 발생하지 않는다.

 

이를 3차원 리스트로 구현했고, 성공할 수 있었다.