99클럽 코테 스터디 15일차 TIL + Dijkstra

문제

Baekjoon2665: 미로만들기

• 설명: 검은 방, 흰 방으로 이루어져있는 격자 모양의 방들이 있다. 검은 방을 최소한으로 지나면서 (0, 0)에서 (n - 1, n - 1)로 이동하라.

풀이

• 흰방으로 이동할 때의 가중치를 $0$, 검은방으로 이동할 때의 가중치를 $1$라고 하자.
• 이때 가중치를 가장 작도록 (0, 0)에서 (n - 1, n - 1)로 이동하려면 최단거리로 이동하면 된다.
• 즉, 다익스트라를 사용해 풀어준다.

오늘의 회고

• 삼항 연산자를 잘못써서 오류를 잡는데 시간을 오래 썼다.
• Python의 삼항 연산자(조건부 연산자)는 기본적으로 연산자 우선순위가 굉장히 낮다. 따라서 아래와 같은 코드는

  1 + 0 if False else 1

• 아래와 같이 동작하므로

  (1 + 0) if False else 1

• 답은 1이 나온다. 삼항 연산자를 먼저 계산하도록 하고 싶다면 아래와 같이 괄호로 묶어준다.

  1 + (0 if False else 1)

Code

# Baekjoon02665.py
import sys
from queue import PriorityQueue

input = sys.stdin.readline

MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]

n = int(input())
room = [input().rstrip() for _ in range(n)]

pq = PriorityQueue()
pq.put((0, (0, 0))) # (거리, (행, 열))

visited = [[False] * n for _ in range(n)]

ans = 0
while pq:
    cost, (curr_r, curr_c) = pq.get()

    if curr_r == n - 1 and curr_c == n - 1:
        ans = cost
        break

    if not visited[curr_r][curr_c]:
        visited[curr_r][curr_c] = True

        for dr, dc in MOVES:
            next_r, next_c = curr_r + dr, curr_c + dc
            if (0 <= next_r < n) and (0 <= next_c < n):
                if not visited[next_r][next_c]:
                    # 다음 방문할 노드가 검은방이라면 거리에 1을 더해준다.
                    pq.put((cost + (0 if room[next_r][next_c] == '1' else 1), (next_r, next_c)))

print(ans)