[백준] #18352. 특정 거리의 도시 찾기 (실버 2)

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

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
	int idx;
	int cost;

	// 생성자
	Node(int idx, int cost) {
		this.idx = idx;
		this.cost = cost;
	}

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());  //도시 개수
		int M = Integer.parseInt(st.nextToken());  //도로 개수
		int K = Integer.parseInt(st.nextToken());  //최단 거리
		int X = Integer.parseInt(st.nextToken());  //출발도시 번호

		// 인접 리스트 사용
		List<List<Node>> graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());  //삽입
		}

		// M개의 도로 정보 입력
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());  //시작 도시
			int B = Integer.parseInt(st.nextToken());  //도착 도시
			graph.get(A).add(new Node(B, 1));  //A도시에서 B도시로 가는 도로 존재 (거리 항상 1)
		}

		// 최단 거리 저장 배열
		int[] dist = new int[N + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[X] = 0;  // 출발 도시의 거리 초기화

		// 우선순위 큐 사용
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(X, 0));  //출발지 정점과 가중치를 우선순위 큐에 넣음

		// // 방문 여부를 체크할 배열
		// boolean[] visited = new boolean[N + 1];


		while (!q.isEmpty()) {  //큐에 값이 하나도 없을때까지 반복
			Node now = q.poll();  //큐에서 앞에 있는 노드 반환 및 삭제 (현재 큐에 있는 값 중 출발지로부터 가장 가까운 거리)
			int nowIdx = now.idx;

			// if (visited[nowIdx])  //방문했던 노드라면 패스
			// 	continue;
			// visited[nowIdx] = true;  //방문했다고 표시

			// 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
			// 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
			if (dist[nowIdx] < now.cost) { //해당 노드에 대한 distance값은 여러번 갱신될 수 있어서 큐에 자주 들어갈 수있지만, 한번 방문됐다면 distance의 값은 최소값이다.
				continue;//distance의 값이 더 작으니까 볼 필요없다 -> 이미 방문된 노드이다.
			}// 값이 같은 순간 => distance값이 갱신되서 큐에 들어갔고, 우선순위상 해당 노드가 지금 뽑혔다.
			// distance값이 더 큰 경우가 생기는 이유 => 시작노드에서는 인접노드를 모두 큐에 넣게 되며 거리값을 갱신한다. 그 이후 다른값으로 갱신되더라도, 시작노드때 큐에 넣어놓은 값은 남아있기 때문이다.
			// 그런값을 무시하기 위해 위와같은 조건문을 붙인다.

			for (Node neighbor : graph.get(nowIdx)) {
				if (dist[neighbor.idx] > (dist[nowIdx] + neighbor.cost)) {
					dist[neighbor.idx] = dist[nowIdx] + neighbor.cost;
					q.add(new Node(neighbor.idx, dist[neighbor.idx]));
				}
			}
		}


		boolean check = false;
		for (int i = 1; i <= N; i++) {
			if (dist[i] == K) {  //최단 거리가 K인 모든 도시 출력
				System.out.println(i);
				check = true;
			}
		}
		if (!check) { //최단 거리가 K인 도시가 하나도 존재하지 않으면 -1 출력
			System.out.println(-1);
		}

	}
}

 

주의할 점

1. Node 클래스

>> Comparable<Node> 인터페이스 구현
- Comparable 인터페이스는 Java의 기본 인터페이스 중 하나로, 객체를 자연스럽게 정렬하기 위해 사용
- 이 인터페이스를 구현하려면 compareTo 메서드를 정의해야함!
- Node 클래스가 Comparable<Node>를 구현하고 있으므로, Node 객체 간의 비교가 가능!

 

>> compareTo 메서드
- compareTo 메서드는 두 객체를 비교하여 순서를 결정!
- 이 메서드는 다음과 같은 값을 반환합니다:
   음수: 현재 객체가 비교 대상 객체보다 작을 때
   0: 현재 객체와 비교 대상 객체가 같을 때
   양수: 현재 객체가 비교 대상 객체보다 클 때

>> 우선순위 큐에서의 사용 우선순위 큐(PriorityQueue)는 내부적으로 compareTo 메서드를 사용하여 요소를 정렬합니다.
Node 클래스가 Comparable<Node> 인터페이스를 구현하고 있으므로, 우선순위 큐에서 'Node 객체를 삽입할 때마다' compareTo 메서드를 사용하여 자동으로 정렬합니다. 이로 인해 PriorityQueue<Node>를 사용할 때, cost 값이 가장 작은 Node가 큐의 맨 앞에 위치하게 됩니다.

 

2. 인접 리스트 사용

		List<List<Node>> graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());  //삽입
		}

 

3. 방문배열 대신 아래처럼 사용 가능
꺼낸 노드는 현재 최소 비용을 가지는 노드이기 때문에
해당 노드의 비용이 현재 dist 배열에 기록된 내용보다 크다면 이미 방문된 노드이므로 스킵! (방문한 노드는 이미 최솟값을 가짐!)

			if (dist[nowIdx] < now.cost) {
				continue;//distance의 값이 더 작으니까 볼 필요없다 -> 이미 방문된 노드이다.
			}