[BOJ] 2644 촌수계산 (Java)

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

2644번: 촌수계산

---

1. 문제 요약

차례대로 총 노드 개수 n과 a, b를 입력받고, 간선개수 m, 각각의 관계를 입력받는다.

a에서 b로 가는 간선의 개수를 구하는 문제이다. 

2. 풀이

양방향 bfs, dfs로 풀 수 있다.

처음에는 부모가 존재하고 부모를 타고 가다보면 루트가 존재할 것이라고 생각하여 단방향 그래프로 접근하였다. 또한 부모를 타고 가야하므로 dfs가 적절하다고 생각했다.

하지만 방향을 신경쓸 필요가 없었던게, 입력을 받을 때부터 이미 부모와 자식간의 관계는 확실하다.

우리가 해야할 일은 a에서 b까지 가는 간선의 개수이므로, a에서 b를 찾으러 갈 때도 굳이 단방향으로 찾으러갈 필요가 없다. 즉, a가 부모든 b가 부모든 a에서 b까지 가기만하면 된다는 의미이다. 더군다나 가중치가 없기 때문에 더더욱 방향을 신경써줄 필요가 없다.

 

dfs, bfs 두 가지로 풀었다.

dfs는 기저조건으로 b에 도착하면 min을 갱신하고 return 해주었다.

bfs는 큐에 인접 노드를 넣어줄 때 깊이까지 같이 넣어줬다. 여기서 깊이는 이전 노드 깊이+1을 넣어주었다.

[실행결과]

dfs

bfs

확실히 dfs보다 bfs가 빠르다.

3. 코드

1) dfs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static List<List<Integer>> parent = new ArrayList<> ();
	static int V, E, ans, r1, r2;
	static int p1, p2, min;
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		V = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		p1 = Integer.parseInt(st.nextToken());
		p2 = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(br.readLine());
		visited = new boolean[V+1];

		for (int i = 0; i <= V; i++) {
			parent.add(new ArrayList<> ());
		}
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			parent.get(a).add(b);
			parent.get(b).add(a);
		} //입력 끝
		
		min = Integer.MAX_VALUE;
		dfs(p1, 0);
		if (min == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(min);
	}
	
	static void dfs(int node, int cnt) {
		if (node == p2) { //도착
			min = Math.min(min, cnt);
			//System.out.println(min);
			return;
		}
		
		visited[node] = true;
		int len = parent.get(node).size();
		for (int i = 0; i < len; i++) {
			int n = parent.get(node).get(i);
			if(visited[n]) continue;
			//System.out.println(n+" cnt: "+(cnt+1));
			dfs(n, cnt+1);
			visited[node] = false;
		}
		
		
	}
}

2) bfs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m, from, to, cnt;
	static boolean[] visited;
	static List<List<Integer>> family = new ArrayList<>();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		from = Integer.parseInt(st.nextToken());
		to = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(br.readLine());
		
		//초기화
		visited = new boolean[n+1];
		for (int i = 0; i <= n; i++) {
			family.add(new ArrayList<> ());
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int mem1 = Integer.parseInt(st.nextToken());
			int mem2 = Integer.parseInt(st.nextToken());
			family.get(mem1).add(mem2);
			family.get(mem2).add(mem1); //양방향
		}
		
		bfs();
	}
	
	static void bfs() {
		Queue<Node> queue = new ArrayDeque<> ();
		visited[from] = true;
		queue.offer(new Node(from, 0));
		
		while (!queue.isEmpty()) {
			Node front = queue.poll();
			int len = family.get(front.pos).size();
			for (int i = 0; i < len; i++) {
				int idx = family.get(front.pos).get(i);
				if (visited[idx]) continue;
				
				if (idx == to) {
					System.out.println(front.d+1);
					return;
				}
				
				visited[idx] = true;
				queue.offer(new Node(idx, front.d+1)); //큐에 넣어줄 때 깊이를 같이 넣어줌
			}
		}
		System.out.println(-1);
	}
	static class Node {
		int pos, d;
		public Node(int pos, int d) {
			this.pos = pos;
			this.d = d;
		}
	}
}