mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int[][] map;
	static int[] answer;
	static int cnt;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		map = new int[N + 1][N + 1];
		answer = new int[N + 1];

		st = new StringTokenizer(br.readLine());
		int cr = Integer.parseInt(st.nextToken());
		int cc = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		for (int i = 0; i < M; i++) {

			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			map[n][m] = 1;
			map[m][n] = 1;

		}
		// 입력 종료 & 인접 행렬 생성 종료

		Queue<Integer> q = new LinkedList<>();
		
		// 시작 row 입력
		q.add(cr);
		
		cnt = 1;
		while (!q.isEmpty()) {

			int v = q.poll();

			for (int i = 1; i < map.length; i++) {

				if (map[v][i] == 1) {
					
                    // 방문 여부를 위해 값 변경
					map[v][i] += 1;
					map[i][v] += 1;
					// 탐색하는 열이 구하려는 열과 같은 경우 종료
					if (i == cc) {
						System.out.println(answer[v] + 1);
						return;
					} else {
						answer[i] += answer[v] + 1;
						q.add(i);
					}
				}				
				cnt++;
			}
		}

		// while문을 빠져나왔다는 것은 연결되어 있지 않다는 뜻.
		System.out.println(-1);

	}

}

3. 리뷰

트리를 이용하여 촌수를 계산하는 알고리즘이다.

처음에는 한 행씩 탐색할 때마다 answer++를 해줬는데, 이렇게 되면

도착하는 노드가 아닌 경우에도 answer++이 되어서 값이 다르게 나왔다.

다른 방법을 고민하다가, answer배열을 따로 만들어서

해당 노드를 탐색하면, 부모노드의 배열의 인덱스에 자식 노드로부터 얼마나 떨어져 있는지

더해줬다. 간단하지만 트리 문제는 참 생각할 것이 많은 것 같다.