코딩테스트/[백준] 코딩테스트 연습
그대, 그머가 되어 - 14496번
쵼쥬
2021. 12. 27. 16:50
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int a, b, N, M;
static int count = 0;
static boolean[] visited;
static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
list.get(x1).add(x2);
list.get(x2).add(x1);
}
Queue<Node> pq = new PriorityQueue<>();
pq.add(new Node(a, 0));
while (!pq.isEmpty()) {
Node x = pq.poll();
if (visited[x.num])
continue;
visited[x.num] = true;
if (x.num == b) {
System.out.println(x.count);
return;
}
for (int i : list.get(x.num)) {
if (!visited[i])
pq.add(new Node(i, x.count + 1));
}
}
System.out.println(-1);
}
}
class Node implements Comparable<Node> {
int num, count;
public Node(int num, int count) {
this.num = num;
this.count = count;
}
@Override
public int compareTo(Node o) {
return this.count - o.count;
}
}