인프런 최소 환승 경로

문제

나의 풀이

import java.util.*;

public class TransferRoute {
    public static int solution(int[][] routes, int s, int e) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>(); // key는 역번호, value는 역번호에 연결되어있는 호선들로 이루어진 HashSet
        int n = routes.length;
        for(int i = 0; i < n; i++) { // 각 호선들 정보 탐색
            for(int x : routes[i]) { // i 호선의 역번호들 탐색
                graph.putIfAbsent(x, new HashSet<Integer>()); // x 역번호가 없을 때 새로 생성
                graph.get(x).add(i); // x 역번호와 연결된 i 호선 삽입
            }
        }
        Queue<Integer> q = new LinkedList<>();
        int check[] = new int[n]; // 호선 탐색했는지 여부
        q.offer(s); // 처음역 삽입
        int L = 0; // 환승 횟수
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                int curStop = q.poll(); // 출발역
                for(int line : graph.get(curStop)) { // 출발역에 연결된 호선들
                    if(check[line] == 1) { // 이미 탐색했던 호선인 경우
                        continue; // 넘어가기
                    }
                    check[line] = 1; // 호선 탐색했다고 표시
                    for(int stop : routes[line]) { // 해당 호선의 노선에 있는 역들
                        if(stop == e) { // 도착역이 발견된 경우
                            return L; // 레벨(환승횟수) 리턴해주기
                        }
                        q.offer(stop); // 역번호들 자식 노드로 집어넣기
                    }
                }
            }
            L++; // 환승횟수 증가 
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(TransferRoute.solution(new int[][]{{1, 2, 3, 4, 5, 6, 19}, {2, 7, 8, 13}, {5, 9, 10}, {9, 11, 12, 18}, {13, 14, 15}, {14, 12, 16, 17}}, 1, 12));
    }
}

최소 환승 횟수를 구하는 것이기 때문에 레벨을 환승 횟수로 이용하는 레벨 탐색 사용을 판단해야 한다.
백만개의 역번호를 정점으로 하는 인접리스트를 만든다면 메모리 낭비가 너무 심하기 때문에 해싱을 이용한다. routes를 탐색하여 역번호가 key이고, 호선들을 set 자료구조로 표현한 것을 value로 하는 graph 해쉬를 만든다. 호선 개수만큼 원소를 가진 check 배열 만든다. 레벨 0일 때 s 역을 탐색 시작한다. graph의 1번 역을 찾아서 연결된 호선의 routes에 있는 역들을 큐에 집어 넣는다. 각 레벨을 탐색하면서 큐에 집어 넣기 전에 check 배열에 해당 호선을 체크해주어서 다음으로 넘어갔을 때 체크된 호선일 경우 그 호선에 있는 역들을 큐에 넣지 않고 건너뛰게 해준다. 이렇게 레벨 탐색을 하다가 도착역이 발견 되면 현재 레벨에서 1을 뺀 값이 환승 횟수이므로 이를 리턴해준다.

결과

인프런 벽 허물기

문제

나의 풀이

import java.util.*;

public class Wall {
    public static int solution(int[][] board) {
        int dx[] = {-1, 0, 1, 0}; // 4방향 탐색 위해
        int dy[] = {0, 1, 0, -1};
        int n = board.length;
        int m = board[0].length;
        int cost[][] = new int[n][m]; // 출발점부터 i행 j열까지 가는 데 부숴야 하는 최소 벽의 개수
        for(int i = 0; i < n; i++) {
            Arrays.fill(cost[i], Integer.MAX_VALUE); // 처음에 cost 배열을 최대값으로 채우기
        }
        cost[0][0] = 0; // 출발 지점은 벽 부순 개수 0개
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]); // 다익스트라를 위해 벽의 개수가 적은 것부터 나오도록 우선순위 큐 사용
        pq.add(new int[]{0, 0, 0}); // 0행 0열 부순 개수 0개 넣기
        while(!pq.isEmpty()) { // 다익스트라
            int cur[] = pq.poll();
            if(cur[2] > cost[cur[0]][cur[1]]) { // 우선순위 큐에서 나온 비용값이 기존 cost 배열에 있는 비용값 보다 큰 경우 -> 최소가 아니므로 더 탐색할 필요 x
                continue; // 건너뛰기
            }
            for(int k = 0; k < 4; k++) { // 4방향 탐색
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) { // 격자 밖인 경우
                    continue;
                }
                if(board[nx][ny] == 0 && cost[nx][ny] > cur[2]) { // 갈려고 하는 지점이 통로(부술 필요x)이면서 cost에 있는 비용 값보다 이동할 정점의 비용값이 더 작은 경우
                    cost[nx][ny] = cur[2]; // cost 비용값 갱신
                    pq.offer(new int[]{nx, ny, cur[2]}); // 우선순위 큐에 삽입
                } else if(board[nx][ny] == 1 && cost[nx][ny] > cur[2] + 1) { // 갈려고 하는 지점이 벽이면서 cost에 있는 비용 값 보다 이동할 정점의 비용값 + 1(벽이므로 부숴야함)이 더 작은 경우
                    cost[nx][ny] = cur[2] + 1; // cost 비용값 갱신
                    pq.offer(new int[]{nx, ny, cur[2] + 1}); // 우선순위 큐에 삽입
                }
            }
        }
        return cost[n - 1][m - 1]; // 도착지점의 비용값 반환
    }
    public static void main(String[] args) {
        System.out.println(Wall.solution(new int[][]{{0, 1, 1, 0}, {1, 0, 0, 1}, {0, 1, 0, 0}}));
    }
}

다익스트라를 이용하여 한 정점에서 한 정점으로 가는 최단 거리를 구한다. 다익스트라를 위해 비용 값이 작은 순서대로 동작하는 우선순위 큐를 사용한다. cost는 출발 정점에서 i행 j열 까지 가는 비용인 벽을 부순 횟수를 나타낸다.큐에 정점을 한개 꺼내서 4방향으로 이동시키면서 cost 값을 더 작은 값으로 업데이트 해주는데 cost값이 갱신된 경우 해당 정점을 우선순위 큐에 넣어주는 방식을 반복한다. 우선순위 큐에서 꺼냈을 때의 비용값이 cost의 비용값 보다 큰 경우 뻗을 필요가 없으므로 continue로 넘어간다.

결과