[백준] 2644번 촌수계산 - Java, 자바
난이도
실버2
문제
https://www.acmicpc.net/problem/2644
풀이
코드
package 그래프탐색;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ2644 {
static int N, a, b, res = -1, dist[];
static ArrayList<ArrayList<Integer>> relation = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine()); // 전체 사람 수
dist = new int[N + 1]; // 촌수
for (int i = 0; i < N + 1; i++) {
relation.add(new ArrayList<>());
}
Arrays.fill(dist, -1);
st = new StringTokenizer(br.readLine());
// a, b 의 촌수를 구해야 함
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(br.readLine()); // 관계의 개수
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int p = Integer.parseInt(st.nextToken());
int ch = Integer.parseInt(st.nextToken());
relation.get(p).add(ch);
relation.get(ch).add(p);
}
Queue<Integer> q = new LinkedList<>();
// a와 b의 촌수 찾아야하므로 a부터 출발
dist[a] = 0;
q.add(a);
while (!q.isEmpty()) {
// 확인할 사람 큐에서 빼기
int now = q.poll();
// 비교대상을 찾으면 촌수 저장
if (now == b) {
res = dist[now];
break;
}
// 해당 사람과 관계있는 사람들 확인
for (int tmp : relation.get(now)) {
if (dist[tmp] != -1) continue; // 이미 촌수 확인한 사람이면 pass
dist[tmp] = dist[now] + 1; // 다음 관계는 현재까지 촌수 +1
q.add(tmp);
}
}
System.out.println(res);
}
}
https://namhandong.tistory.com/185
Author And Source
이 문제에 관하여([백준] 2644번 촌수계산 - Java, 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmjieun/백준-2644번-촌수계산-Java-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)