[PRO] 2020 카카오 인턴십 - 경주로 건설(Python/BFS)

🌱 발상 🌱

1️⃣ 전형적인 BFS 문제

• 다른 방식으로도 풀 수 있겠지만 이런 N x N 정사각형 격자 형태는 보통 BFS/DFS 를 많이 선택함
• 최소 비용을 계산해야 한다는 점에서 DFS 보다 BFS 가 더 유리할 것이라고 생각

2️⃣ 우선 순위 큐로 최소 비용을 보장

• 보통 deque 큐를 써서 BFS 문제를 쓰는데 최소 이동 거리가 아닌 최소 비용을 찾는 문제이므로 비용이 더 적은 곳을 먼저 탐색하는 것이 유리

🪴 풀이 🪴

👩🏻‍💻 코드

# BFS
from collections import deque
import heapq

def solution(board):
    INF = 1e8

    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    
    N = len(board)
    visited = [[[INF for _ in range(4)] for _ in range(N)] for _ in range(N)]
    
    q = []
    heapq.heappush(q, [0, 0, 0, -1])
    
    while q:
        cost, x, y, direction = heapq.heappop(q)

        if x == N-1 and y == N-1:
            return cost

        for k in range(4):
            if direction != -1 and (direction + 2) % 4 == k:
                continue
                
            new_x = x + dx[k]
            new_y = y + dy[k]
            new_cost = cost
            
            if direction == k or direction == -1:
                new_cost += 100
            else:
                new_cost += 600
            
            if new_x < 0 or new_x >= N or new_y < 0 or new_y >= N or board[new_x][new_y] == 1 or visited[new_x][new_y][k] < new_cost:
                continue
            else:
                visited[new_x][new_y][k] = new_cost
                heapq.heappush(q, [new_cost, new_x, new_y, k])

1️⃣ 변수 선언

• INF: 무한대를 저장할 변수
• dx, dy: x축 방향, y축 방향 변화량
• N: 정사각형 크기
• visited: 각 칸에 도달하는 최소 비용이 저장된 3차원 배열. 각 칸에 들어온 방향을 함께 저장해야 하기 때문에 3차원으로 선언
• q: 우선 순위 큐. [비용, 현재 x, 현재 y, 현재 칸에 들어온 방향] 들로 구성된 요소를 저장함

2️⃣ BFS 탐색

• 우선순위 큐의 첫 요소 초기화
  • (0,0)의 위치에 0원의 비용으로 초기화 함
  • 시작 지점에서 방향은 자유로우므로 -1 로 방향을 넣음
  • visited[0][0] 은 모든 방향에서 최솟값이 0이므로 [0,0,0,0]으로 초기화
• (N-1, N-1) 도착 시 return
  • 우선순위 큐로 진행했으므로 가장 먼저 도착한 요소가 가장 적은 비용임을 보장
• 4방향으로 이동
  • 만약 현재 위치가 시작점이 아니고 이전에 왔던 방향으로 돌아가는 방향이면 진행하지 않음
  • 다음 칸에 대한 정보 초기화(new_x, new_y, new_cost)
    • 만약 이전과 같은 방향으로 진행 → 직선 도로 사용 → 100원 추가
    • 다른 방향으로 진행 → 코너 + 직선 도로사용 → 100 + 500 = 600 원 추가
  • 만약 다음 칸이 도면을 벗어나거나, 이미 다음 칸을 동일한 방향으로 더 저렴한 비용에 방문할 수 있다면 진행하지 않음
  • 진행가능 하면 visited 의 비용을 갱신하고, 우선순위 큐에 다음 칸을 삽입

---

🌻 후기 🌻

🤔 생각해볼 점

• 최소 비용 문제에선 우선 순위 큐를 잘 활용해보자

🆕 새롭게 알게 된 점

없음

🏛️삽질기

1. 방향 고려 안함 TC 14번 실패

   처음엔 visited 를 boolean 값으로 진행했었음. 14번이 실패하는 것을 보고 방향을 도입

2. 우선 순위 큐 안 씀 TC 11번 실패

   그냥 큐로 구현했을 때 시간 초과가 나서 우선순위 큐를 써서 최적화 함