(1249) [D4] 보급로

문제 🌐

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다. 전투가 진행 중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다. 그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지나갈 수 없다. 전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다. 공병대는 출발지(S)에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.

출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.

깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

image

지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다. 출발지는 좌상단의 칸 (S)이고 도착지는 우하단의 칸(G)가 된다. 이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다. 지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.

image

이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다. 따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다. 지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다. 출발지(S)와 도착지(G)는 좌상단과 우상단이 되고 입력 데이터에서는 0으로 표시된다.

출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다. 다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.

image

입력

가장 첫 줄은 전체 테스트케이스의 수이다.

각 테스트케이스마다 지도의 크기 (N×N)가 주어진다. 지도의 크기는 최대 100 x 100이다.

그 다음 줄부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

출력

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

접근 방법

가중치가 있는 최소비용 찾기 문제다.

기본적으로 bfs를 통해 접근하지만, 가장 중요한 것은 방문 처리를 했다고 해서 그 지점을 그냥 지나치면 안 된다는 것이다. 따라서 Node 클래스를 만들고 경로를 지나면서 나온 비용 cost를 저장했다.

시험에서는 이런 식으로 계산했다.

현재 도착한 노드에서 주변 노드를 살펴보는데,

  1. 이때 방문하지 않았다면 무조건 값을 현재 노드의 cost + 가중치 로 갱신해 준다.
  2. 방문했을 때는 cnt배열에 저장된 값 cnt(next)과 현재 경로를 통해 계산한 가중치 cnt(now) + cost와 비교하여 갱신한다.

시험을 치고 나와서 비슷한 문제가 있었다는 걸 기억하고 다시 살펴보니… Priority Queue라는 좋은 도구를 사용했더라. pq의 정렬 기준을 Node 클래스의 cost 기준으로 잡았다. cost가 가장 적게 든 노드부터 하나씩 꺼내는 것이다.

사실 아직 Comparator를 사용하는 연습이 충분하지 않아 시험에서는 쓸 생각을 못 했다. 그래서 조건문 겁나 썼던….

static class Node implements Comparable<Node>{
	int r;
	int c;
	int cost;
	
	public Node(int r, int c, int cost) {
		super();
		this.r = r;
		this.c = c;
		this.cost = cost;
	}
		@Override
	public int compareTo(Node o) {
		return Integer.compare(this.cost, o.cost);
	}
}

그리고 지금 와서 확인해 보니, weight 배열의 초기값을 Integer.MAX_VALUE로 갱신할 경우는 방문 배열은 따로 처리하지 않아도 됐었다. 값이 Integer.MAX_VALUE보다 작은 경우에는 당연히 방문한 게 되니까~! 그리고 혹시 이전에 값이 갱신되었을 경우 정수 최대값과 비교하는 조건문과 같기 때문이다. PQ를 이용해 비용이 가장 작은 노드부터 탐색하면서 (N-1, N-1)에 도착했을 때 탐색을 종료했다.

int r = 0;
int c = 0;
q.add(new Node(r, c, 0));
weight[r][c] = map[r][c];
	while (true) {
	Node curr = q.poll();
	r = curr.r;
	c = curr.c;
	if (r == N - 1 && c == N - 1)
		break;
	
	if (visited[r][c]) continue;
	
	visited[r][c] = true;
	for (int d = 0; d < 4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N)
			continue;
			if (weight[nr][nc] > map[nr][nc] + weight[r][c]) {
			weight[nr][nc] = map[nr][nc] + weight[r][c]; 
			q.add(new Node(nr, nc, weight[nr][nc]));
		}
	}
}
System.out.println("#" + test_case + " " + weight[N - 1][N - 1]);

Full Solution

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static class Node implements Comparable<Node>{
        int r;
        int c;
        int cost;

        public Node(int r, int c, int cost) {
            super();
            this.r = r;
            this.c = c;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] dr = { 0, 0, -1, 1 };
        int[] dc = { -1, 1, 0, 0 };

        for (int test_case = 1; test_case <= T; test_case++) {
            PriorityQueue<Node> q = new PriorityQueue<>();
            int N = sc.nextInt();
            int[][] map = new int[N][N];
            int[][] weight = new int[N][N];
            boolean[][] visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                String s = sc.next();
                for (int j = 0; j < N; j++) {
                    map[i][j] = s.charAt(j) - '0';
                    weight[i][j] = Integer.MAX_VALUE;
                }
            }

            int r = 0;
            int c = 0;
            q.add(new Node(r, c, 0));
            weight[r][c] = map[r][c];

            while (true) {
                Node curr = q.poll();
                r = curr.r;
                c = curr.c;
                if (r == N - 1 && c == N - 1)
                    break;

                if (visited[r][c]) continue;

                visited[r][c] = true;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                        continue;

                    if (weight[nr][nc] > map[nr][nc] + weight[r][c]) {
                        weight[nr][nc] = map[nr][nc] + weight[r][c]; 
                        q.add(new Node(nr, nc, weight[nr][nc]));
                    }
                }
            }
            System.out.println("#" + test_case + " " + weight[N - 1][N - 1]);
        }
    }

}