[BOJ - JAVA] 17404 - RGB 거리 2 (다익스트라, DP)

# 주소

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

# 문제

# 문제 해설 및 코드 리뷰

package cod;
import java.util.*;
class Dickstra{
	int x;
	int y;
	int cost;
	Dickstra(int x, int y,int cost){
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
}
public class BOJ17404 {
	static int n;
	static PriorityQueue<Dickstra> queue;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		int[][] arr = new int[n][3];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < 3; j++)
				arr[i][j] = scan.nextInt();
		int max = Integer.MAX_VALUE;
		for(int a = 0; a < 3; a++) {
			int[][] dp = new int[n][3];
			dp[0][a] = arr[0][a];
			for(int i = 1; i < n; i++)
				for(int j = 0; j < 3; j++)
					dp[i][j] = 10000000;
			queue = new PriorityQueue<Dickstra>((o1, o2) -> (o1.cost - o2.cost));
			queue.offer(new Dickstra(0, a, arr[0][a]));
			while(!queue.isEmpty()) {
				Dickstra now = queue.poll();
				if(now.x == n - 1) {
					max = Math.min(max, now.cost);
					continue;
				}
				for(int i = 0; i < 3; i++) {
					if(now.y == i) continue;
					if(now.x + 1 == n - 1 && a == i) continue;
					if(dp[now.x + 1][i] > now.cost + arr[now.x + 1][i]) {
						dp[now.x + 1][i] = now.cost + arr[now.x + 1][i];
						queue.offer(new Dickstra(now.x + 1, i, now.cost + arr[now.x + 1][i]));
					}
				}
			}
		}
		System.out.println(max);
	}
}

저는 DP를 잘 못해서 DP 연습겸 풀까 하다가, 예전에 공부를 하면서 다익스트라도 DP에 속한다는 것이 기억나, 다익스트라로 풀었던 문제입니다.

채점 순위는 하위권이었지만 (아무래도 DP의 정통방식 풀이 속도가 넘사벽) 이런 방식으로 시도해볼 수 있어 좋았습니다.

문제를 뜯어보며, 왜 다익스트라로 풀 때에도 이 문제가 풀리는지 확인해봅시다.

		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		int[][] arr = new int[n][3];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < 3; j++)
				arr[i][j] = scan.nextInt();
		int max = Integer.MAX_VALUE;

입력은 다음과 같습니다. 

총 n개의 행에 3개의 열을 입력 받으므로 n x 3크기의 배열을 지정해주고 입력 받습니다.

for(int a = 0; a < 3; a++) {
    int[][] dp = new int[n][3];
    dp[0][a] = arr[0][a];
    for(int i = 1; i < n; i++)
        for(int j = 0; j < 3; j++)
            dp[i][j] = 10000000;
    queue = new PriorityQueue<Dickstra>((o1, o2) -> (o1.cost - o2.cost));
    queue.offer(new Dickstra(0, a, arr[0][a]));

이후 n x 3크기의 dp배열을 선언합니다.

이 dp배열의 최초 값은 10000000을 삽입하며, 0행의 값에는 arr값을 삽입합니다.

for문을 사용한 이유는 R, G, B 총 3개의 값 중 1개씩 돌아가며 출발할건데 이 3개 중 어떤 것으로 시작하는지에 따라 정답이 달라질 수 있기 때문입니다.

문제의 조건상, 1행에는 1개의 색만 사용 가능하며 위,아래의 색은 달라야 하기 때문에 QUEUE에 들어갈 시작 값을 for문을 통해 분기시켜주어야 하는 것입니다.

가중치의 오름차순에 따라 값을 갱신하므로 우선순위큐를 사용합니다.

while(!queue.isEmpty()) {
        Dickstra now = queue.poll();
        if(now.x == n - 1) {
            max = Math.min(max, now.cost);
            continue;
        }
        for(int i = 0; i < 3; i++) {
            if(now.y == i) continue;
            if(now.x + 1 == n - 1 && a == i) continue;
            if(dp[now.x + 1][i] > now.cost + arr[now.x + 1][i]) {
                dp[now.x + 1][i] = now.cost + arr[now.x + 1][i];
                queue.offer(new Dickstra(now.x + 1, i, now.cost + arr[now.x + 1][i]));
            }
        }
    }

1) now.y 가 i와 같으면 continue;

2) 마지막 행에서 최초의 시작점에서 사용했던 색과 i가 같으면 continue;를 한 뒤, dp의 새로 갱신할 값이 now.cost + arr값보다 작으면 dp를 갱신해주고 queue에 삽입합니다. 최초의 방문시에는 dp의 값이 10000000이기 때문에 이보다 작은 arr값의 특성상 어떤 값을 넣어도 갱신 가능하며, 만약 값이 터무니 없이 크다하더라도 저희는 visit처리를 하지 않았기 때문에 다익스트라 특성상 언제든지 값이 뒤에서 갱신될 수 있습니다.

보통의 다익스트라는 값을 갱신하면 visit을 사용하여 방문 여부를 체크하지만 이 문제는 보다시피 visit처리가 필요 없습니다.

왜그럴까요?

첫 째로는 행을 갱신하는 now.x의 값은, queue에 삽입됨에 따라 now.x + 1이 되며 계속해서 1씩 증가하는 모습을 보여주고 있으며, 두 번째로는 뒤에서 뒤따라오는 queue에 삽입되어있던 값들이 방문한 값이라 할지라도 최솟값이면 새로 갱신할 여지가 있기 때문입니다.

분명 기존의 다익스트라에서 사용되는 visit과는 조금 차이점이 있을 수 있습니다.

기존의 다익스트라에서 사용되던 visit처리는, 노드에 대한 처리이지 다음과 같이 n x 3에 대한 처리를 하려면 2차원 배열을 사용해야 하기 때문입니다. 저는 이 문제에서는 특히, visit이 필요 없다 생각하여 이를 빼고 작성하여 정답이 될 수 있었습니다.

만약 visit이 들어간 로직을 짜고 싶다면, 2차원 배열로 작성하셔야 겠습니다. 한 번 방문한 visit[i][j]는 continue해주시고, 아닐 경우 true로 만드는 것입니다. 하지만 이는 별로 필요 없는 로직입니다. 아까도 설명드렸다시피 애초에 행값은 1씩 추가하며 더해주고 있고 계속해서 오름차순으로 삽입되기 때문입니다. (visit써도 정답 처리 됩니다)

그리하여

if(now.x == n - 1) {
    max = Math.min(max, now.cost);
    continue;
}

now.x가 n - 1에 도달할 때 max값을 갱신해주고 정답으로 가장 작은 max를 출력하면 되겠습니다.

이 문제는 최초의 rgb값 중 어떤 것을 사용하느냐에 따라 3가지 루트가 바뀌는 것을 확인하였습니다.

그 때 그 때 최솟값을 갱신할 수 있는 DP로 짤 수도 있겠지만 저는 다익스트라로 풀이를 시도해 보았습니다.

다익스트라 역시 DP에 속하기 때문에 시간복잡도 측면에서 그리 큰 차이가 나지 않는 것도 확인하였습니다.

감사합니다 :)