백준 16166 서울의 지하철 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/16166

풀이는 다음과 같다.

import java.io.*;
import java.util.*;


public class Main {
    //호선 최대 10개
    //역 최대 100개
    static ArrayList<Integer>[] A = new ArrayList[101]; //같은역, 다른호선들  (A[1] = {2, 3} 1번 역이 2호선 3호선 걸침)
    static ArrayList<Integer>[] B = new ArrayList[11]; //같은호선, 다른역들 (B[3] = {4, 5} 3호선은 4번역 5번역 가짐)
    static HashMap<Integer, Integer> map = new HashMap<>(); //역 번호 2^(32-1) 까지니까, 따로 줄여줘야함. 해당 내용을 아래의 idx로 수행

    static boolean[][] visited = new boolean[11][101]; //2차원배열 이유는, 같은 역이더래도 해당 역의 호선에 따라 여러번 세줄 수 있음.
    //예를 들어, 1호선 2호선이 3번역을 가지고 있을때, visited[1][3]과 visited[2][3]은 각각의 방문 배열이라는 소리다.


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0 ; i < 11 ; i++) {
            B[i] = new ArrayList<Integer>();
        }

        for(int i = 0 ; i <= 100 ; i++) {
            A[i] = new ArrayList<Integer>();
        }



        int N = Integer.parseInt(br.readLine());
        int idx = 1;

        for(int i = 1 ; i <= N ; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken()); //역의 수

            for(int j = 1 ; j <= K ;j++) {
                int num = Integer.parseInt(st.nextToken());

				//여기가 입력값 역 숫자를 내 idx로 바꿔주는 로직
                if(!map.containsKey(num)) { 
                    map.put(num, idx);
                    A[idx].add(i);
                    B[i].add(idx);
                    idx++;
                }
                else {
                    A[map.get(num)].add(i);
                    B[i].add(map.get(num));
                }
            }

        }

        int end =Integer.parseInt(br.readLine());
        //여기까지 초깃값세팅


        bw.write(String.valueOf(BFS(end)));
        bw.flush();
        bw.close();

    }

    static int BFS(int end) {
        int answer = -1;

        PriorityQueue<Station> q = new PriorityQueue<>();

        for(int i = 0 ; i < A[map.get(0)].size() ; i++) {
            q.add(new Station(0, map.get(0), A[map.get(0)].get(i))); //0번역 호선들 기록해서 추가해줌
            //보면, map.get으로 넣어주므로 입력받은 역의 숫자가 아니라, map에 저장해놓은 idx가 나오게 된다.
        }

        while(!q.isEmpty()) {
            Station curStation = q.poll();

            if(curStation.num == map.get(end)) {
                answer = curStation.cnt;
                return answer;
            }

            int curCnt = curStation.cnt;
            int curNum = curStation.num;
            int curLine = curStation.line;

            for(int i = 0 ; i < B[curLine].size() ; i++) { //같은호선의 다른 역들 환승없이 큐에 넣기
                int nextNum = B[curLine].get(i);
                if(!visited[curLine][nextNum]) {
                    visited[curLine][nextNum] = true;
                    q.add(new Station(curCnt, nextNum, curLine));
                }
            }

            for(int i = 0 ; i < A[curNum].size() ; i++) { //같은역의 다른 호선들 환승있이 큐에 넣기
                int nextLine = A[curNum].get(i);
                if(!visited[nextLine][curNum]) {
                    visited[nextLine][curNum] = true;
                    q.add(new Station(curCnt+1, curNum, nextLine));
                }
            }


        }

        return answer; 
        //큐 다 빌때까지 answer이 curStation.cnt로 갱신되지 않으면,
        //환승을 통해 갈 수 없는 역이니 처음에 설정해준 -1 그대로 실행됨.
    }




    static class Station implements Comparable<Station> {
        int cnt; //환승
        int num; //역번호
        int line; //호선

        public Station (int cnt, int num, int line) {
            this.cnt = cnt;
            this.num = num;
            this.line = line;
        }

        public int compareTo(Station e) {
            if(this.cnt > e.cnt) return 1;
            else return -1;
        }
    }

}

최소 환승 알고리즘이다.
다익스트라에 조금 더 많은것들을 요한다.
(https://www.youtube.com/watch?v=XIwiZZr2l5I)

최소 거리가 아니라, 최소 환승 횟수라고 생각하고 다익스트라를 적용해야 한다.

주석을 읽으며 헷갈릴 부분을 정리하자면,

일반 BFS와 다르게,
큐에서 원소 하나를 뽑고,
해당 원소에 관해서 큐에 추가할 내용이 두가지이다.

• 해당 역과 같은 호선을 가진 역들을 큐에 추가
  (호선이 같아 환승 추가 없이)

for(int i = 0 ; i < B[curLine].size() ; i++) { //같은호선의 다른 역들 환승없이 큐에 넣기
                int nextNum = B[curLine].get(i);
                if(!visited[curLine][nextNum]) {
                    visited[curLine][nextNum] = true;
                    q.add(new Station(curCnt, nextNum, curLine));
                }
            }

• 해당 역의 다른 호선들을 큐에 추가
  (호선이 다르니 환승을 추가해서)

for(int i = 0 ; i < A[curNum].size() ; i++) { //같은역의 다른 호선들 환승있이 큐에 넣기
                int nextLine = A[curNum].get(i);
                if(!visited[nextLine][curNum]) {
                    visited[nextLine][curNum] = true;
                    q.add(new Station(curCnt+1, curNum, nextLine));
                    //curCnt+1이 환승 추가라는 뜻
                }
            }

또한 visited배열이 2차원인것,
HashMap을 사용해서 실제 입력값이 아닌 내 idx를 사용한것이다.
해당 내용은 주석에 설명이 되어있다.

문제가 쉽지 않았다. 개인적으로 골드 3은 되어야 하지 않을까... 라고 생각한다

A배열과 B배열을 사용하면서도 헷갈렸고,
해당 내용에 역숫자를 idx로 바꿔서 코드를 짜서, 그부분이 헷갈렸다..
머릿속에서 톱니바퀴 움직이듯 전부 다 짜맞춰지면 좋으련만..
아무쪼록 어려운 문제를 간만에 풀어서,
더 노력해야겠다는 생각을 했다.