1-1. 정답 코드

import copy
from collections import deque


def solution(board):
    m = len(board)
    n = len(board[0])
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(m):
        for j in range(n):
            if board[i][j] == 1:
                board[i][j] = 'w'
            else:
                board[i][j] = float('inf')
    board[0][0] = 0

    def bfs(start):
        graph = copy.deepcopy(board)
        q = deque([start])
        while q:
            x, y, cost, previous_dir = q.popleft()
            for new_dir in range(4):
                nx = x + dx[new_dir]
                ny = y + dy[new_dir]
                if previous_dir != new_dir:
                    new_cost = cost + 600
                else:
                    new_cost = cost + 100
                if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] != 'w' and graph[nx][ny] > new_cost:
                    graph[nx][ny] = new_cost
                    q.append((nx, ny, new_cost, new_dir))
        return graph[m - 1][n - 1]

    # 두 개의 방향으로 시작
    return min(bfs((0, 0, 0, 3)), bfs((0, 0, 0, 2)))

1-2. 오답 코드

import copy
from collections import deque


def solution(board):
    m = len(board)
    n = len(board[0])
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(m):
        for j in range(n):
            if board[i][j] == 1:
                board[i][j] = 'w'
            else:
                board[i][j] = float('inf')
    board[0][0] = 0

    def bfs(start):
        graph = copy.deepcopy(board)
        q = deque([start])
        while q:
            x, y, previous_dir = q.popleft()
            for new_dir in range(4):
                nx = x + dx[new_dir]
                ny = y + dy[new_dir]
                if previous_dir != new_dir:
                    cost = graph[x][y] + 600
                else:
                    cost = graph[x][y] + 100
                if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] != 'w' and graph[nx][ny] > cost:
                    graph[nx][ny] = cost
                    q.append((nx, ny, new_dir))
        return graph[m - 1][n - 1]

    # 두 개의 방향으로 시작
    return min(bfs((0, 0, 3)), bfs((0, 0, 1)))

---

2. 후기

# 정답 코드
# 사용되는 이유: 방향의 존재, 해당 좌표가 코너일 경우 최단비용을 보장하지 않는다.
q.append((nx, ny, new_cost, new_dir)) 

# 오답 코드
q.append((nx, ny, new_dir))

그동안 BFS 문제를 풀 때, 큐에 좌표를 저장하는 일은 많았지만, 좌표의 현재 좌표값까지 같이 저장한 경우는 없었다.

그도 그럴 것이 popleft()로 꺼낸 좌표(=(x,y))를 이용하면 graph[x][y]값을 얻을 수 있기 때문이다. 그리고 보통은 최적의 값을 구해야 하기 때문에 최단거리를 보장하는 새로운 값으로 최신화 되곤 한다.

하지만 이 문제에서 중요한 건 최신화된 값이 아니다. 어떤 방향으로 해당 좌표의 가격으로 도착했는지가 중요하다. 좌표에 도착한 순간은 더 작은 값을 가질 수 있어도 도착한 좌표가 코너일 경우 코너의 다음 좌표에서는 코너 건설비용을 포함한 더 큰 값을 가질 수 있기 때문이다.

---

2-1. 예시

값을 따로 저장하지 않았을 때 생기는 오류이다.

1번 그림을 봤을 때, 도착에 들어갈 값은 1900이 되어야한다고 예상할 수 있다.

1. (3,5)가 처음으로 꺼내져서 코너인 (4,5)의 좌표값을 얻어낸다.

graph[4][5] = 1800
q.append((4, 5, 아래 방향))

2. 그 다음으로 (4,4)가 꺼내져서 코너의 좌표값을 최신화 시킨다.

graph[4][5] = 1600
q.append((4, 5, 오른쪽 방향))

3. 이제 코너인 (4,5)가 꺼내진다. 도착지점에는 잘못된 값인 1700이 저장된다.

x, y, previous_dir = q.popleft()
# 4, 5, 아래 방향 = q.popleft()
...
...
cost = graph[x][y] + 100
# 1700 = 1600 + 100
...
...
graph[nx][ny] = cost
# graph[도착][도착] = 1700

정답 코드를 사용해도 작동과정은 위와 동일하다.
하지만 어떤 방향으로 좌표에 도착했을 때의 가격이 존재한다.
q = [(4, 5, 1800, 아래 방향), ... (4, 5, 1600, 오른쪽 방향)]