白駿2644号:計数

問題の説明

インチの関係をグラフィックで表すことができます.

これは2人の図形上の距離を求める問題である.

方法

データは隣接リストなので、HashMapを使用しました.

重みを持たないグラフィック距離はBFSの深さで計算できる.

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]//size 1=1
1の値をとり、アクセス可能な場所を決定します.
2,3,4にアクセスできるので、キューに2,3,4を入れます.
while(--size 1>=0)終了後、キュー:[2,3,4]//size 2=3
2、3、4を取り出してアクセス可能な場所を決定します.
5,6,7,8にアクセスできるので、キューに5,6,7,8を入れます.
while(--size 2>=0)が終了すると、キュー:[5,6,7,8]//size 3=4
5、6、7、8を取り出して、アクセス可能な場所を決定します.
アクセスできる場所がないのでqは空になり、外のドアは閉まっています.

正解

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;
	}

}