[백준] #14496. 그대, 그머가 되어 (실버 2)

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

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 a = Integer.parseInt(st.nextToken());  //바꾸려는 문자
		int b = Integer.parseInt(st.nextToken());  //바꿀 문자

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());  //전체 문자의 수
		int M = 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 x = Integer.parseInt(st.nextToken());  //시작
			int y = Integer.parseInt(st.nextToken());  //도착
			graph.get(x).add(new Node(y, 1));  // x에서 y로 가는 간선 (가중치 1로 설정)
			graph.get(y).add(new Node(x, 1));  // y에서 x로 가는 간선 (양방향)
		}

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

		// 우선순위 큐 사용
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(a, 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) {
				continue; //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]));
				}
			}
		}
		if (dist[b] == Integer.MAX_VALUE) {
			System.out.println(-1); // 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1 출력
		} else {
			System.out.println(dist[b]); // a를 b로 바꾸기 위한 최소 치환 횟수(가중치 1로 설정해서 횟수와 같음)
		}
	}
}

 

주의할 점

1. 양방향
문제에서 "치환 가능한 문자쌍"이라고 했을 때, 이 쌍은 양방향으로 치환이 가능하다는 의미!

			graph.get(x).add(new Node(y, 1));  // x에서 y로 가는 간선 (가중치 1로 설정)
			graph.get(y).add(new Node(x, 1));  // y에서 x로 가는 간선 (양방향)

 

2. 가중치를 1로 설정하여 dist[b]는 a를 b로 바꾸기 위한 최소 치환 횟수라고 할 수 있음!