[BAEKJOON] 2644 촌수계산

문제 요약

• 알고리즘 분류: BFS, DFS
• 난이도: Silver2
• 문제
  • 내용:
• 사이트: https://www.acmicpc.net/problem/2644

문제풀이

 

Code

Python

 

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		Map<Integer, List<Integer>> adj = new HashMap<>();
		int N = Integer.parseInt(br.readLine());

		for (int i = 1; i <= N; i++) {
			adj.put(i, new ArrayList<>());
		}

		StringTokenizer st = new StringTokenizer(br.readLine());
		int from = Integer.parseInt(st.nextToken());
		int to = Integer.parseInt(st.nextToken());
		int count = Integer.parseInt(br.readLine());

		for (int i = 0; i <  count; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
			adj.get(b).add(a);
		}

		int[] visited = new int[N + 1];
		Arrays.fill(visited, -1);

		Stack<Integer> stack = new Stack<>();
		stack.add(from);
		visited[from] = 0;

		while (!stack.empty()){
			int now = stack.pop();
			for(Integer node : adj.get(now)){
				if(visited[node] == -1){
					visited[node] = visited[now] + 1;
					stack.add(node);
				}
			}
		}

		System.out.println(visited[to]);

	}
}