문제 요약
사람 수 n이 주어지고, 촌수를 계산해야 하는 두 사람 nodeA, nodeB가 주어진다.
이후 m개의 부모-자식 관계(간선)가 주어질 때, 두 사람 사이의 촌수(최단 거리) 를 구하는 문제다.
두 사람이 연결되어 있지 않다면 -1을 출력한다.
핵심 아이디어
이 문제는 “사람 = 정점, 부모-자식 관계 = 간선”으로 보면, 두 정점 사이의 최단 거리(간선 개수)를 구하는 문제다.
간선 가중치가 전부 1이므로 BFS를 돌리면 nodeA에서 nodeB까지의 최단 촌수를 구할 수 있다.
입력 처리 & 인접 리스트 구성
입력으로 들어오는 관계는 (left, right) 형태지만, 촌수는 위/아래 구분 없이 연결만 되면 되므로 무방향 그래프로 만든다.
adjList.get(left).add(right)adjList.get(right).add(left)
for (int i = 0; i < node + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < line; i++) {
StringTokenizer input = new StringTokenizer(br.readLine());
int left = Integer.parseInt(input.nextToken());
int right = Integer.parseInt(input.nextToken());
adjList.get(left).add(right);
adjList.get(right).add(left);
}정렬은 이 문제에서 필수는 아니지만(정답이 거리만이라), 디버깅/순서 재현 관점에서 넣어도 괜찮다.
BFS 설계(큐에 거리까지 같이 넣기)
큐 상태
int[]{현재 사람, 촌수(거리)}형태로 큐에 넣는다.
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{start, 0});
visited[start] = true;방문 처리 위치
BFS는 큐에 넣는 순간 visited 처리를 해야, 같은 정점이 여러 번 큐에 들어가는 걸 방지할 수 있다.
지금 코드도 그 방식으로 잘 되어 있다.
종료 로직(빠른 탈출)
이 코드의 포인트는 “target을 발견하면 즉시 종료”다.
if (a == target){
distance = temp[1] + 1;
break loop;
}- 장점: target을 찾는 순간 바로 끝내서 불필요한 탐색을 줄일 수 있다.
- 이 방식이 안전한 이유: BFS 특성상 “처음 도달한 거리”가 최단거리이기 때문.
또한 처음 distance = -1로 잡아두고 끝까지 못 찾으면 그대로 -1이 출력되게 만든 점도 문제 요구사항과 맞다.
전체 코드(제출용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int node;
static int line;
static int nodeA;
static int nodeB;
static List<List<Integer>> adjList = new ArrayList<>();
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
node = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
nodeA = Integer.parseInt(st.nextToken());
nodeB = Integer.parseInt(st.nextToken());
line = Integer.parseInt(br.readLine());
for (int i = 0; i < node + 1; i++) adjList.add(new ArrayList<>());
for (int i = 0; i < line; i++) {
StringTokenizer input = new StringTokenizer(br.readLine());
int left = Integer.parseInt(input.nextToken());
int right = Integer.parseInt(input.nextToken());
adjList.get(left).add(right);
adjList.get(right).add(left);
}
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}
visited = new boolean[node + 1];
bfs(nodeA, nodeB);
}
static void bfs(int start, int target) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{start, 0});
visited[start] = true;
int distance = -1;
loop:
while (!q.isEmpty()) {
int[] temp = q.poll();
for (int a : adjList.get(temp[0])) {
if (!visited[a]) {
visited[a] = true;
q.add(new int[]{a, temp[1] + 1});
if (a == target) {
distance = temp[1] + 1;
break loop;
}
}
}
}
System.out.println(distance);
}
}보완하면 더 좋은 점(선택)
start == target이면 BFS 들어가기 전에 0을 바로 출력하면 더 깔끔하다(촌수 0).- 굳이
loop:라벨을 쓰지 않고,poll()직후if (temp[0] == target)로 처리해도 동일하게 구현 가능하다(큐에{node, dist}를 들고 있으니까).
Eazy하게