문제 풀이

이 문제는 어떤 호선에 어떤 역이 있는지, 어떤역은 어떤 호선에 포함되는지의 정보를 모두 가지고 있어야한다.

그러므로 두개의 배열을 사용했는데 배열 a에는 어떤 호선에 어떤 역들이 있는지를 저장하고
배열 b에는 어떤 역이 어떤 호선에 포함되어있는지 역번호에 따른 호선의 정보들을 저장한다.

여기서 주의할 점은 역번호는 최대 232 - 1의 정수가 입력된다.
b배열의 인덱스에는 역의 번호가 들어가야하는데 배열의 길이를 억단위를 넘게 할당 받을 순 없다.
(ex - b[2100000000])

그러므로 역 번호에 해당하는 새로운 인덱스를 할당하도록 한다.
HashMap을 이용해서 역 번호를 key로 두고 value값은 입력된 순서에따라 인덱스를 부여한다.

물론 이미 인덱스가 부여된 역 번호를 또 다시 입력받을 경우에는 HashMap에서 인덱스 번호를 꺼내어 쓰면된다.

그러고 나서는 환승 횟수가 적은 순으로 정렬을하는 우선순위 큐를 사용해서 문제를 풀어나가면 된다.

먼저 우선순위큐에 환승횟수가 0이고 역번호 0에 해당하는 인덱스, 그리고 해당하는 호선을 가지는 데이터를 넣어주고 bfs를 시작한다.

현재 호선에 포함된 아직 방문하지않은 모든 역을 우선순위큐에 넣어주고.(호선을 옮기지 않았으므로 환승 횟수는 그대로)

현재의 역이 포함된 아직 방문하지 않은 모든 호선을 우선순위 큐에 넣어주면된다. (호선을 옮겼으므로 환승 횟수는 +1)

현재 역이 입력받은 도착역이면 환승 횟수를 출력하고 끝내면된다.

문제 링크

boj/16166

소스코드

PS/16166.java

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


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        static int N;
        static List<Integer>[] a = new ArrayList[11];
        static List<Integer>[] b = new ArrayList[110];
        static Map<Integer, Integer> map=new HashMap<>();
        static boolean[][] visit = new boolean[11][110];

        static class Entity implements Comparable<Entity>
        {
            int cnt,num,line;

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

            @Override
            public int compareTo(Entity o) {
                if(this.cnt == o.cnt)
                {
                    if(num == o.num)
                    {
                        return this.line - o.line;
                    }
                    else
                        return this.num-o.num;
                }
                else
                    return this.cnt -o.cnt;
            }
        }
        public static void main(String[] args) throws IOException {
            N = Integer.parseInt(br.readLine());
            for (int i = 0; i <= N; i++) {
                a[i] = new ArrayList<>();
            }
            for(int i=0;i<110;i++)
            {
                b[i] = new ArrayList<>();
            }
            int idx =0 ;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int k = Integer.parseInt(st.nextToken());
                for (int j = 0; j < k; j++) {
                    int num = Integer.parseInt(st.nextToken());
                    if(!map.containsKey(num)) {
                        map.put(num,++idx);
                        b[idx].add(i+1);
                        a[i+1].add(idx);
                    }
                   else
                    {
                        b[map.get(num)].add(i+1);
                        a[i+1].add(map.get(num));
                    }
                }
            }
            int e = Integer.parseInt(br.readLine());
            int e_idx;
            if(map.containsKey(e))
                e_idx = map.get(e);
            else
            {
                bw.write("-1");
                bw.flush();
                return;
            }
            //map 번호의 인덱스
            //b[인덱스] - 인덱스에 해당하는 번호가 속해있는 호선
            //a[i] - i 호선에 속해있는 번호
            PriorityQueue<Entity> pq = new PriorityQueue();
            for(int i=0;i<b[map.get(0)].size();i++) {
                pq.add(new Entity(0, map.get(0),b[map.get(0)].get(i)));
            }

            while(!pq.isEmpty())
            {
                int curNum = pq.peek().num;
                int curLine = pq.peek().line;
                int curCnt = pq.peek().cnt;
                pq.poll();
                if(curNum == e_idx)
                {
                    bw.write(Integer.toString(curCnt));
                    bw.flush();
                    return;
                }
                for(int i=0;i<a[curLine].size();i++)
                {
                    int nextNum = a[curLine].get(i);
                    if(!visit[curLine][nextNum]) {
                        visit[curLine][nextNum] =true;
                        pq.add(new Entity(curCnt, nextNum, curLine));
                    }
                }
                for(int i=0;i<b[curNum].size();i++)
                {
                    int nextLine = b[curNum].get(i);
                    if(!visit[nextLine][curNum]) {
                        visit[nextLine][curNum] =true;
                        pq.add(new Entity(curCnt + 1, curNum, nextLine));
                    }
                }
            }

            bw.write("-1");
            bw.flush();


        }

    }