문제 설명

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.
전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.

그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.
전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.
공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.
도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.

출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.
깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

그림 1 (a) 파손된 도로 (b) 지도 형태와 이동 방향

지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다.
출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)가 된다.

이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다.
지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.

그림 2 지도 정보

이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다.
따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다.

지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다.
출발지(S)와 도착지(G)는 좌상단과 우하단이 되고 입력 데이터에서는 0으로 표시된다.
출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다.

다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.

[입력]

가장 첫 줄은 전체 테스트케이스의 수이다.
각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.
그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

[출력]

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.
같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

입력
10
4
0100
1110
1011
1010
6
011001
010100
010011
101001
010101
111010
8 . . .

input.txt

출력
#1 2
#2 2
. . .

output.txt

문제 요약) 뭐가 말이 많은데 시작점에서 도착점까지 가는 경로 위에 적힌 값의 합의 최소를 구하면 됩니다.

풀이 과정

“2차원 맵에서 가중치가 있는 최단 경로를 구하는 문제”

상하좌우 이동 + 최단 경로 구하는 문제라서 잠시 BFS를 생각할 수도 있겠지만 가중치가 하나로 고정되어 있는 문제가 아니라 간선마다 가중치가 다른 문제이기 때문에 다익스트라 알고리즘을 사용해야 합니다.

정답 코드

import heapq as hq
 
T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    # 도로의 값 입력
    road = [[] for _ in range(N)]
    for i in range(N):
        road[i] = list(map(int, list(input())))
        
    # 10의 8제곱 즉, 1억을 최대값으로 설정
    INF = 1e8
    # distances[x][y]는 (x, y)까지의 최단 거리를 뜻합니다
    # 각 위치까지의 최단 거리 값을 INF로 초기화
    distances = [[INF for _ in range(N)] for _ in range(N)]
    
    # 상하좌우 이동을 위한 방향 벡터
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
		
    # 최단거리를 구하기 위한 다익스트라 알고리즘 구현
    def dijkstra(start_x, start_y):
        # 최소힙(우선순위 큐) 사용
        min_heap = []
        # 시작점까지의 최단 거리를 road의 시작점에 적힌 값으로 초기화
        distances[start_x][start_y] = road[start_x][start_y]
        # 최소힙에 (시작점까지의 최단 거리, 시작점의 x좌표, 시작점의 y좌표) 튜플 형식으로 값을 저장
        # 튜플의 맨 앞에 있는 최단 거리를 기준으로, 힙의 루트에는 항상 거리의 최솟값이 위치한다
        hq.heappush(min_heap, (distances[start_x][start_y], start_x, start_y))
         
        # 힙이 빌 때까지 아래 로직을 반복
        while min_heap:
            # 최단 거리와 그 위치의 x,y 좌표를 힙에서 pop
            now_distance, now_x, now_y = hq.heappop(min_heap)
 
            # 현재 좌표에 이미 더 짧은 거리로 방문된 적이 있으면
            if distances[now_x][now_y] < now_distance:
                # 지금 경로는 무시해라
                continue
                
            # 상하좌우 이동
            for d in range(4):
                # 상하좌우 좌표값
                nx = now_x + dx[d]
                ny = now_y + dy[d]
                # 이동하려는 상하좌우 좌표값이 road 범위를 벗어나지 않는지 확인
                if 0 <= nx < N and 0 <= ny < N:
                    # 현재까지의 누적 거리에서 (nx, ny) 좌표까지 갔을 때의 거리를 계산
                    new_distance = now_distance + road[nx][ny]
                    # 그 거리가 원래 적혀있던 (nx, ny)까지의 최단 거리보다 작다면
                    if new_distance < distances[nx][ny]:
                        # (nx, ny)까지의 최단 거리를 그 거리로 업데이트
                        distances[nx][ny] = new_distance
                        # 새로 찾은 최단 거리, nx, ny 좌표를 힙에 push
                        hq.heappush(min_heap, (distances[nx][ny], nx, ny))
		                    
    # (0,0)을 시작점으로 해서 최단 거리 찾기
    dijkstra(0, 0)
     
    # (N-1, N-1)까지의 최단 거리를 출력
    print("#%d %d" % (test_case, distances[N-1][N-1]))

다익스트라는 힙(= 우선순위 큐)를 써서 현재까지 발견한 경로 중 가장 짧은 거리부터 꺼냅니다. 이때, 같은 좌표가 여러 번 큐에 들어갈 수 있습니다.

그러나 이미 그 노드를 더 짧은 거리로 방문한 적이 있다면, 그보다 긴 거리로 다시 방문하는 건 불필요할 겁니다. 그래서 distances[now_x][now_y] < now_distance 조건을 만족할 때엔 continue로 그 경로를 건너뜁니다.

예를 들어 A -3-> B -1-> C / A -10-> C 이렇게 시작점 A에서 시작해서 도착점 C로 가는 경로가 여러 개면
1. A→B→C (4) / 2. A→C (10) 으로 점 C에 대한 값은 힙에 두 번 들어가게 됩니다. → 힙 = [(4, C), (10, C)]

이때, (10, C)가 꺼내졌을 때는 이미 C까지의 거리가 4로 저장되어 있을 것이기 때문에 C까지 10이 걸리는 경로는 더이상 확인하지 않아도 됩니다.

그 아래 로직에서는 유효한 상하좌우 좌표값을 확인하면서 현재 위치 (now_x, now_y)를 거쳐서 (nx, ny)까지 가는 경로가 원래 적힌 값보다 작다면 그 값으로 distances[nx][ny] 값을 업데이트 해서 시작점 (0,0)에서부터 모든 좌표까지의 최단 거리를 구했습니다.

이상입니다.

LIST