[BOJ/PYTHON] 2423. 전구를 켜라 (최단 경로 - 다익스트라)

백준 문제 링크: https://www.acmicpc.net/problem/2423

문제 요약

N × M 직사각형 크기의 전자 회로에서 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결

전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜짐

전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값 구하기

핵심 아이디어

불가능할 경우 "NO SOLUTION”을 출력해야 하는데, N + M이 홀수인 경우 물리적으로 불을 켜는 것이 불가능하다.

다익스트라로 푼다고 가정했을 때 비용값을 구하는 것이 필요한데, ‘돌려야 하는 칸의 개수의 최솟값’을 구해야 하기 때문에 돌릴 필요가 없으면 0, 돌려야 하면 1로 비용을 산정하면 된다.

• “/”일 때는 (i, j+1)에서 (i+1, j) 방향으로 향할 때 비용이 0, 나머지 방향은 비용이 1
• “\”일 때는 (i, j)에서 (i+1, j+1) 방향으로 향할 때 비용이 0, 나머지 방향은 비용이 1

이렇게 하면 정점 좌표, 비용이 존재하는 다익스트라로 풀면 된다.

풀이

# gold1-2423. 전구를 켜라

import sys, heapq
input = sys.stdin.readline
INF = int(1e9) # 무한

# 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결
# 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜짐
# 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값
# 문제에서 주어진 경로가 0 뒤집은 경로가 1로 하면 그거로 거리 구할 수 있음. 

n, m = map(int, input().split()) # N × M 직사각형 크기의 전자 회로
graph = [[[] for _ in range(m+1)] for _ in range(n+1)]
distance = [[INF] * (m+1) for _ in range(n + 1)]

for i in range(n):
    row = input()
    for j in range(m):
        # 주어진 대로 이동하면 비용 0, 뒤집으면 비용 1
        if row[j] == '/':
            top = 0 # 오른쪽 위로 향하는 대각선 -> 본인 비용 0
            bottom = 1 # 왼쪽 아래로 향하는 대각선 -> 뒤집어야 하니까 비용 1
        else: # "\\"
            top = 1 # 위로 향하는 대각선 -> 뒤집어야 해서 비용 1
            bottom = 0
        graph[i][j].append((i+1, j+1, bottom)) # \\
        graph[i+1][j+1].append((i, j, bottom))
        graph[i+1][j].append((i, j+1, top)) # /
        graph[i][j+1].append((i+1, j, top))        

def dijkstra():
    distance[0][0] = 0
    q = [(0, 0, 0)]
    while q:
        dist, i, j = heapq.heappop(q)
        if distance[i][j] != dist: continue
        for new_i, new_j, new_dist in graph[i][j]:
            if distance[new_i][new_j] > dist + new_dist:
                distance[new_i][new_j] = dist + new_dist
                heapq.heappush(q, (dist + new_dist, new_i, new_j))

if (n + m) % 2 == 1:
    print("NO SOLUTION")
else: 
    dijkstra()
    print(distance[-1][-1])

top, bottom값을 변수로 정의하고 다음과 같이 한 이유는 \인 케이스와 /인 케이스 각각 그래프에 append할 때 의미 없이 8줄(graph[i][j], graph[i+1][j+1], graph[i+1][j], graph[i][j+1]에 비용 1 1 0 0, 0 0 1 1을 일일이 적어줘야 함)을 쓰게 되는 일을 줄이기 위해서이다.

graph[i][j].append((i+1, j+1, bottom)) # \\
graph[i+1][j+1].append((i, j, bottom))
graph[i+1][j].append((i, j+1, top)) # /
graph[i][j+1].append((i+1, j, top))

Trouble Shooting

저게 다익스트라로 풀릴 수가 있는지 한참 고민했다.

실행 시간

메모리 146588KB, 시간 780ms (python3)