[백준 스터디 5주차] 1719 택배 골드4 - 자바(Java) / 다익스트라

📑 문제

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

1719번: 택배

문제

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

이와 같은 경로표를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경로가 주어지는데, 두 집하장의 번호와 그 사이를 오가는데 필요한 시간이 순서대로 주어진다. 집하장의 번호들과 경로의 소요시간은 모두 1000이하의 자연수이다.

 

출력

예시된 것과 같은 형식의 경로표를 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 다익스트라를 매 집하장마다 돌아주는 것으로 풀었다.

 N개의 집하장 중 하나에서, 남은 다른 N-1개의 집하장 중 하나로 가는 경로표를 모두 만들어야 하므로, 이 코드는 총 세 번의 루프를 돌게 풀었다.

1️⃣ 출발 집하장을 1번부터 N번 집하장까지 설정하는 for문

2️⃣ (다익스트라) 매 상태마다 최소 가중치 노드(current로 설정할 노드)를 찾는 for문.

3️⃣ (다익스트라) 2번에서 찾은 최소가중치 노드에 연결되어있는 N-1개의 노드를 탐색하여, 최소 가중치를 업데이트 하는 for문.

 

 

---

 

 >> 저장 변수

🗂️ int[][] containers: 가중치를 저장하는 인접행렬 배열.

🗂️ int[][] outputs: 결과로 출력할 경로표. output[i][j]는 i번 집하장에서 j번 집하장으로 갈 때 가장 먼저 거치는 집하장 번호를 갖는다.

 

 >> 다익스트라 알고리즘

🗂️ boolean[][] visited:

🗂️ int[] temp: 1️⃣번 루프에서 설정된 출발 집하장이 다른 집하장까지 가는데 걸리는 최소 가중치를 담을 변수. 루프 시작 부분에서 미리 인풋으로 받은 가중치를 containers 변수에서 복사해온다.  

 

---

 

 

 ◻️ 1️⃣번 루프에서 매 출발 집하장을 current 노드(시작 노드)로 설정하고, 가중치 변수 temp를 설정한다.

 

 ◻️ current 노드(최소가중치 노드)에 연결된 노드들을 살펴본다. (3️⃣번 루프)

 

 ◻️ 연결된 노드들은 거기까지 가는 경로 비용이 최소 가중치로 업데이트 되는 것을 뜻한다.

 

 ◻️ 만약 current노드가 출발 집하장(1️⃣번 루프)이면, current 노드에 연결된 노드(k)들은 출발 집하장이 가장 먼저 거치는 집하장이 된다. 따라서 이 노드들의 번호를 output[출발집하장=current][k] 배열에 넣어준다.

 

 ◻️ 만약 current노드가 출발 집하장이 아니면, 여기에 연결된 노드(k)들은 output[출발집하장][current]에 저장된 값을 그대로 output[출발집하장][k]에 넣어준다.

 예를 들어 1번 집하장에서 2번>5번>6번 순으로 연결되어 간다고 할 때, 1번 집하장에서 5번, 6번 집하장으로 가기 위해 가장 먼저 거치는 집하장은 모두 2번 집하장이 되므로, output[1][2]=2 >> output[1][5]=output[1][2] >> output[1][6]=output[1][5]가 되는 것이다. 

 

 ◻️ 3️⃣번 루프가 끝나면 경로 가중치가 제일 작은 노드가 다음에 탐색할 current 노드가 된다.(2️⃣번 루프 반복)

 

 

 

 

 

 

 

🙋‍♀️ 의견

 다익스트라의 개념을 다시 한 번 다질 수 있는 문제였다고 생각한다.

 효율성은...........잘 모르겠다. 플루이드-워샬 알고리즘으로도 풀 수 있겠지만, 난 다익스트라 원길을 걷기에(ㅎㅎ)

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_1719_택배_골드IV {

	static boolean[] visited;
	static int N, M;
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] containers = new int[N+1][N+1];
		int[][] outputs = new int[N+1][N+1];
		visited = new boolean[N+1];
	
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			containers[v1][v2] = containers[v2][v1] = weight;
		}// input
		
	
		for (int i = 1; i <= N; i++) {	//각 시작점(행)에 대하여
			int current=i;
			int[] temp = Arrays.copyOf(containers[i], N+1);

			for (int j = 1; j <= N; j++) {	// N개의 current 노드 확인
				int min=Integer.MAX_VALUE, minVertex=current;
				visited[current]=true;
				
				for (int k = 1; k <= N; k++) {	// current노드에 연결되어있는 것들 확인	
					if(containers[current][k]==0 || visited[k]) continue;
					if(containers[current][k] != 0 && !visited[k]) {
						if(current == i) {
							outputs[i][k] = k;
						}else {
							if(temp[k]==0) {
								temp[k] = temp[current] + containers[current][k];
								outputs[i][k] = outputs[i][current];								
							}else {
								if(temp[current] + containers[current][k] < temp[k]) {
									temp[k] = temp[current] + containers[current][k];
									outputs[i][k] = outputs[i][current];
								}
							}
						}
					}
				}//최소비용 노드에 연결된 노드들

				// 최소비용노드를 current로 업데이트
				for (int t = 1; t <= N; t++) {
					if(t==current || visited[t]) continue;
					if(temp[t]!=0 && temp[t] < min) {
						min = temp[t];
						minVertex = t;
					}
				}		
				current = minVertex;

			}
			clearIsVisited();
		}

		
		for (int i = 1; i <= N; i++) {	//print
			for (int j = 1; j <= N; j++) {
				if(i==j) System.out.print("- ");
				else System.out.print(outputs[i][j]+" ");
			}
			System.out.println();
		}
		
	}//end of main
	
	static void clearIsVisited() {
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}
	}
}//end of class

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨