[Java] leetcode 815. Bus Routes

문제

Bus Routes - LeetCode

Bus Routes - LeetCode

버스 탄 총 횟수를 구하는 문제

 

알아야 할 개념

자바

• 인접 리스트
• 해시맵 HashMap<Integer , ArrayList<Integer> > 구조
• https://0713k.tistory.com/30 

[Java] leetcode 200. Number of Islands

풀이

POV : 그래프 dfs 탐색을 어떻게 구현할 것인가? 가 핵심 포인트.

로직은 다음과 같다. 

1. 주어진 정류장을 그래프화한다.
2. 그래프를 탐색하여 source, target까지 버스 갈아탄 횟수를 기록한다.
3. 정답을 리턴한다.

 

문제 풀이는 간단하다. 인접 리스트로 그래프 dfs 탐색 하듯이, 주어진 버스 노선들을 인접 리스트에 담고 탐색을 쭈루룩 하면 된다. 하지만 

HashMap< Integer, List<ArrayList> > map = new HashMap<>();

다음과 같이 hashmap 안에 다른 자료구조가 들어간 구조가 처음이라면 이 문제가 상당히 난해하다. 자바에서는 map 안에 리스트를 만들기 위해 코드를 조금 더 작성해야 한다. 

 

위 사진은 리트코드 예제 1,2 의 [번호,line] 구조를 시각적으로 나타냈다.

우선 해시맵으로 [ 정류장 번호, 버스 Line ] 을 매핑해줘야한다.

        for(int i = 0 ; i < routes.length ;i++){
            int Line = i;
            for(int j =0 ;j < routes[i].length; j++){
                int busNum = routes[i][j];
                map.computeIfAbsent(busNum,x-> new ArrayList<Integer>());
                map.get(busNum).add(Line);
            }
        }

그 다음 각 버스 정류장을 탐색 하면  OK.

        while(!Q.isEmpty()){
            int size = Q.size();
            for(int i= 0 ;i < size ;i++){
                int curBusNum = Q.poll();
                //정류장에 연결된 버스 Line을 가져온다. 
                for(int nextLine : map.get(curBusNum)){
                	//아직 탐색 안한 버스 Line 만 탐색
                    if(!v[nextLine]){
                        v[nextLine] = true;
                        //현재 Line의 정류장 번호 다 탐색해서 정답이면 리턴
                        for(int nextBus : routes[nextLine]){
                            if(nextBus == target) return level;
                            if(map.get(nextBus).size() > 1) Q.offer(nextBus);
                        }
                    }
                }
            }
            level++;
        }

 

코드

자바

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        boolean v[] = new boolean[routes.length];
        if(source == target) return 0;
        for(int i = 0 ; i < routes.length ;i++){
            int Line = i;
            for(int j =0 ;j < routes[i].length; j++){
                int busNum = routes[i][j];
                map.computeIfAbsent(busNum,x-> new ArrayList<Integer>());
                map.get(busNum).add(Line);
            }
        }
        // curBunNum , distance
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(source);
        int level =1 ;
        while(!Q.isEmpty()){
            int size = Q.size();
            for(int i= 0 ;i < size ;i++){
                int curBusNum = Q.poll();
                for(int nextLine : map.get(curBusNum)){
                    if(!v[nextLine]){
                        v[nextLine] = true;
                        for(int nextBus : routes[nextLine]){
                            if(nextBus == target) return level;
                            if(map.get(nextBus).size() > 1) Q.offer(nextBus);
                        }
                    }
                }
            }
            level++;
        }
        return -1;
    }
}