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

접근 방법 🧐

나는 dfs, bfs가 너무 어렵다..
우선 어떤 방법으로 풀어야할지도 감이 안 잡혀서 다른 분들의 글을 보다가 내 나름대로 기준을 정해봤다.
나만의 DFS BFS 판단 방법!

• 관계가 전혀 없어서 촌수를 계산 할 수 없으면 -1 출력
  
  
• 관계를 찾아야하는 노드들끼리의 촌수를 찾아야한다.
  →하나를 기준 노드로 두고 그 노드로부터 다른 노드까지의 경로(간선 수) 찾기
  
  
• 관계는 양방향이다!! 입력받은 x와 y의 관계 양쪽에 관계를 지정해줘야한다.
  
  
• 하나의 부모는 여러명의 자식을 가질 수 있다.
  → ArrayList<>타입의 배열을 각 노드에 지정해줘서, 여러명의 자식 정보를 담을 수 있도록 하자

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;

public class Main {
	static ArrayList<Integer>[] relation;
	static int[] visited;
	static int n, a, b;
	static int result=0;
	static boolean check = false;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine()); //전체 사람의 수
		
		relation = new ArrayList[n+1]; //관계 저장
		visited = new int[n+1];
		
		for(int i=0;i<=n;i++) {
			relation[i] = new ArrayList<Integer>();
		}
		
		st = new StringTokenizer(br.readLine()); //두 사람의 번호
		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 x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			relation[x].add(y); //양방향
			relation[y].add(x); //관계 있으면 1로
		}
		
		BFS(a,b);
		
		bw.write(check ? visited[b]+"": "-1");
		bw.flush();
		bw.close();
		
	}
	
	public static void BFS(int parent, int child) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.offer(parent);
		
		while(!queue.isEmpty()) {
			int currNode = queue.poll();
			
			if(currNode == child) {
				check = true;
				return;
			}
			
			for(int next : relation[currNode]) {
				if(visited[next] == 0) {
					visited[next] = visited[currNode]+1;
					queue.offer(next);
				}
			}
		}
		
	}

}

느낀점 📖

이번 알고리즘 스터디 문제집 중에 처음으로 풀었던 문제였다.
그림을 그리고 간선을 따라, 해당 노드를 찾아가다보니, 이건 경로 찾기와 비슷한 문제구나!
인 것 까지는 알았는데,
1. 부모에게 여러 자식이 있는 것을 처리하는 법을 생각하기 까지가 오래걸렸고
2. 촌수를 계산할 때 그냥 cnt로 지나갈 때 ++해주는 것이 아니라 이전 노드의 visited에 담겨있는 값에 +1씩 해줘야한다.
    →이걸 생각 못해서 구글링을 통해 이해했다..