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