백준 5214 (환승) - java

https://www.acmicpc.net/problem/5214

5214번: 환승

 

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

 

유형 : BFS 

 

접근 방식

• 환승 유형의 문제이다. (노드들간의 묶음단위 탐색 유형 : 내가 지은거임 ㅋㅋㅋㅋ)
• 우선 그림을 통해 이해할 필요가 있다.

주어진 예시

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

 

그림

그림을 아주 못그린다.... 이해 부탁

그림을 통해 우리가 알 수 있는 것은 두 가지이다.

• 동일한 차선에서의 탐색이 가능하다.
• 하나의 지점이 2개 이상의 차선을 보유하고 있다면 환승할 수 있다.

위 문제에서 가장 중요한 것은 방문 처리이다.

개인적으로 BFS 유형의 어려운 그래프 탐색 문제는 방문 탐색이 파악하기 어렵다.

 

결론부터 말하자면 해당 문제(환승)는 방문 처리가 2번 필요하다. (지점에 대하여 + 차선에 대하여)

• 한번 방문한 지점에서 탐색이 진행된다면 해당 지점을 굳이 다시 볼 필요는 없다.
• 차선 또한 마찬가지이다. 한번 탐색한 차선을 2번 이상 탐색할 필요가 없다.

입력 정리

        for(int i=1;i<=k;i++){
            cube[i] = new ArrayList<>();

            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=m;j++){
                int tmp = Integer.parseInt(st.nextToken());

                station[tmp].add(i);
                cube[i].add(tmp);
            }
        }

 

2개의 그래프를 생성한다. (station : 해당 지점이 연결된 차선의 종류들 , cube : 해당 차선이 보유한 지점들)

• 위 코드에서 i값은 하이퍼 큐브(차선)의 값이다.
• tmp의 값은 지점의 값이다.

탐색

for(int cur : station[1]){
            pq.add(new Node(1,cur,1));
            vCube[cur] = true;
        }

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.num == 1 && n == 1){
                System.out.println(1);
                return;
            }

            for(int nextNode : cube[cur.cube]){

                if(nextNode == n){
                    System.out.println(cur.count + 1);
                    return;
                }

                if(!vNum[nextNode]){
                    vNum[nextNode] = true;
                    pq.add(new Node(nextNode,cur.cube,cur.count + 1));

                    for(int nextCube : station[nextNode]){
                        if(!vCube[nextCube]){
                            vCube[nextCube] = true;
                            pq.add(new Node(nextNode,nextCube,cur.count+1));
                        }
                    }
                }

            }
        }

 

탐색을 진행하는 과정을 기술하겠다.

• 우선 시작 지점(1)과 연결된 차선을 전부 큐에 집어넣는다. 
• 탐색 과정
  • 현재 차선의 정보를 클래스에 보유하고 있어야 한다.
  • 현재 차선으로부터 아직 방문하지 않은 지점들을 방문 처리한다.
    • 방문 처리가 이번에 수행된 지점들이 다른 차선을 보유하고 있고 방문하지 않은 차선이라면 방문 처리한다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int k = 0;

    static ArrayList<Integer>[] station;
    static ArrayList<Integer>[] cube;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());


        station = new ArrayList[n+1];
        cube = new ArrayList[k+1];

        for(int i=1;i<=n;i++){
            station[i] = new ArrayList<>();
        }

        for(int i=1;i<=k;i++){
            cube[i] = new ArrayList<>();

            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=m;j++){
                int tmp = Integer.parseInt(st.nextToken());

                station[tmp].add(i);
                cube[i].add(tmp);
            }
        }


        search();

        br.close();
    }

    static void search(){
        boolean[] vNum = new boolean[n+1];
        boolean[] vCube = new boolean[k+1];

        vNum[1] =  true;
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.count - y.count
        );

        for(int cur : station[1]){
            pq.add(new Node(1,cur,1));
            vCube[cur] = true;
        }

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.num == 1 && n == 1){
                System.out.println(1);
                return;
            }

            for(int nextNode : cube[cur.cube]){

                if(nextNode == n){
                    System.out.println(cur.count + 1);
                    return;
                }

                if(!vNum[nextNode]){
                    vNum[nextNode] = true;
                    pq.add(new Node(nextNode,cur.cube,cur.count + 1));

                    for(int nextCube : station[nextNode]){
                        if(!vCube[nextCube]){
                            vCube[nextCube] = true;
                            pq.add(new Node(nextNode,nextCube,cur.count+1));
                        }
                    }
                }

            }
        }

        System.out.println(-1);
    }
}
class Node{
    int num;
    int cube;
    int count;

    Node(int num,int cube,int count){
        this.num = num;
        this.cube = cube;
        this.count = count;
    }
}