백준 2644번: 촌수계산

문제 설명

• 촌수관계를 그래프로 나타낼 수 있습니다.
• 두 사람의 그래프상의 거리를 구하는 문제입니다.

접근법

• 데이터가 인접리스트로 주어졌기 때문에 HashMap을 활용했습니다.
• 가중치가 없는 그래프의 거리는 BFS의 depth로 구할 수 있습니다.

pseudocode

main(){
	AddToMap();입력 데이터를 활용해 HashMap을 만듭니다.
    if(BFS가 target을 찾았으면){
    	몇번만에 찾았는지를 출력합니다.
    }else{ // 타겟을 못찾았으면
    	-1을 출력합니다.
    }
}

AddToMap(a,b,HashMap){
	// 양방향 그래프이기 때문에 a가 key인 경우, b가 key인경우를 모두 입력해줘야 합니다.
	// a를 key로 쓰는 경우
	if(HashMap의 key에 a가 없으면){
    	HashMap에 key와 value가 (a,[b])인 값을 추가해라.
    }else{	// HashMap의 key에 a가 있으면
    	HashMap의 a값([num1,num2...])에 b를 추가해라 // -> a:[num1,num2,...b]
    }
    // b를 key로 쓰는 경우
	if(HashMap의 key에 b가 없으면){
    	HashMap에 key와 value가 (b,[a])인 값을 추가해라.
    }else{	// HashMap의 key에 b가 있으면
    	HashMap의 b값([num1,num2...])에 a를 추가해라 // -> b:[num1,num2,...a]
    }
	//아래 정답에서는 if(key값이 있으면)으로 코딩했습니다.
}

BFS(start,target){
	q와 방문여부를 만듭니다.
    처음 start값을 q에 넣고 방문처리 합니다.
    while(q가 빌 때까지){
    	깊이를 1 증가시킵니다.
        현재시점의 q 크기
    	while(현재시점의 q만큼만 꺼냅니다){
        	int now = q에서 꺼낸 값
            for(q에서 꺼낸 값에서 갈 수 있는 위치){
            	if(해당 위치를 방문했으면) continue;
                if(해당 위치가 내가 찾던 그 위치면) return true;
                해당 위치 방문처리
                해당 위치 큐에 더하기
            }
        }
    }

}

• BFS의 너비는 큐의 변화를 생각하면 쉽습니다.
  다음과 같은 그래프가 존재하며 1에서 시작하는 경우를 생각해 보겠습니다.
  

시작 시점의 큐 : [1] // size1 = 1
1의 값을 꺼내어 방문가능한 위치를 확인합니다.
2,3,4를 방문할 수 있기 때문에 큐에 2,3,4를 넣습니다.

while(--size1>=0)이 끝난 뒤 큐 : [2,3,4] // size2 = 3
2,3,4를 꺼내면서 방문 가능한 위치를 확인합니다.
5,6,7,8을 방문할 수 있기 때문에 큐에 5,6,7,8을 넣습니다.

while(--size2>=0)이 끝난 뒤 큐 : [5,6,7,8] // size3 = 4
5,6,7,8을 꺼내면서 방문 가능한 위치를 확인합니다.
방문할 수 있는 곳이 없기때문에 q가 비게되고 바깥쪽 while문이 종료됩니다.

정답

import java.util.*;

public class Main {
	static int depth = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int start = sc.nextInt();
		int target = sc.nextInt();
		int m = sc.nextInt();
		HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
		for (int i = 0; i < m; i++) {
			int a1 = sc.nextInt();
			int a2 = sc.nextInt();
			AddToMap(a1, a2, map);
		}
		if (BFS(start, target, map, N)) {
			System.out.println(depth);
		} else {
			System.out.println(-1);
		}
	}

	public static void AddToMap(int a1, int a2, HashMap<Integer, List<Integer>> map) {
		//a1을 key값으로 검사합니다.
		if (map.containsKey(a1)) { // a1이 key로 존재하면 -> ArrayList의 value를 가지고 있다는 의미입니다.
			map.get(a1).add(a2); // a1의 value(ArrayList)에 a2를 추가합니다.
		} else { // a1이 key로 존재하지 않으면 -> ArrayList가 아직 만들어지지 않았다는 의미입니다.
			List<Integer> temp = new ArrayList<Integer>(); 
			temp.add(a2); 
			map.put(a1, temp); // a1이 키, a2를 담은 ArrayList가 value입니다.  
		}
		
		//a2를 key값으로 검사합니다. 바로 위 코드와 구조적으로 완벽히 동일합니다.
		if (map.containsKey(a2)) {
			map.get(a2).add(a1);
		} else {
			List<Integer> temp = new ArrayList<Integer>();
			temp.add(a1);
			map.put(a2, temp);
		}

	}

	public static boolean BFS(int start, int target, HashMap<Integer, List<Integer>> map, int N) {
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] v = new boolean[N + 1]; // 사람을 1부터 표현했기 때문에 0번자리를 사용하지 않고 N+1칸을 만들었습니다.
		// 처음 입력값을 큐에 추가 및 방문처리 합니다. 
		q.add(start);
		v[start] = true;
		while (!q.isEmpty()) { // 큐가 빌때까지 반복합니다.
			//queue의 크기만큼의 while문을 하나 더 생성하면 이는 depth마다 끊어서 돌리겠다는 의미입니다.
			depth++;
			int size = q.size();
			while (--size >= 0) {
				int now = q.poll();
				for (Integer i : map.get(now)) {
					if (v[i]) continue; // i를 이미 확인했다면 넘깁니다.
					if (i == target) return true;// i가 내가 찾는 사람이라면 BFS를 멈추고 true를 반환합니다.						
					// 계속해서 BFS를 진행합니다.
					v[i] = true;
					q.add(i);
				}
			}
		}
		//target을 찾지 못한 경우입니다.
		return false;
	}

}