ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

Algorithm/Baekjoon

[Java] ๋ฐฑ์ค€ 5214๋ฒˆ - ํ™˜์Šน

๊ฐœ๋ฐœ๊ฐœ๊ตด๐Ÿธ 2022. 7. 18. 22:00

[๋ฌธ์ œ]

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

 

5214๋ฒˆ: ํ™˜์Šน

์ฒซ์งธ ์ค„์— ์—ญ์˜ ์ˆ˜ N๊ณผ ํ•œ ํ•˜์ดํผํŠœ๋ธŒ๊ฐ€ ์„œ๋กœ ์—ฐ๊ฒฐํ•˜๋Š” ์—ญ์˜ ๊ฐœ์ˆ˜ K, ํ•˜์ดํผํŠœ๋ธŒ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) ๋‹ค์Œ M๊ฐœ ์ค„์—๋Š” ํ•˜์ดํผํŠœ๋ธŒ์˜ ์ •๋ณด๊ฐ€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด

www.acmicpc.net

[ํ’€์ด]

BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)์„ ์ด์šฉํ•˜์—ฌ ํ’€์ดํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์˜ค๋Š” ์ˆซ์ž๋“ค์„ 2๊ฐœ๋กœ ๋‚˜๋ˆ„์–ด ์ƒ๊ฐํ•˜์˜€์Šต๋‹ˆ๋‹ค.

tubeOut ๊ฐ ํ•˜์ดํ”„ํŠœ๋ธŒ๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์—ญ ๋ฒˆํ˜ธ

tubeIn ๊ฐ ์—ญ๋“ค์ด ์ด๋™ํ•  ์ˆ˜ ์ž‡๋Š” ํ•˜์ดํ”„ํŠœ๋ธŒ ๋ฒˆํ˜ธ

 

๋”ฐ๋ผ์„œ ์˜ˆ์‹œ 1๋ฒˆ์„ ์‚ฌ์šฉํ•˜๋ฉด tubeOut๊ณผ tubeIn๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์„ฑ๋ฉ๋‹ˆ๋‹ค.

๋‘ ArrayList๋ฅผ ํ™œ์šฉํ•ด์„œ findStation()๋ฅผ ํ†ตํ•ด BFS๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด,

 

( ์ด๋•Œ N = 1์ด๋ผ๋ฉด ๋ฌด์ €๊ฑด 1๋ฒˆ๋งŒ์— ์—ญ์— ์ด๋™ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์˜ˆ์™ธ ์ฒ˜๋ฆฌ๋ฅผ ํ•˜์ง€ ๋ชปํ•ด 100%์—์„œ ์˜ค๋‹ต์ฒ˜๋ฆฌ๊ฐ€ ๋˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ–ˆ์—ˆ์Šต๋‹ˆ๋‹ค. )

 

1๋ฒˆ ์—ญ -> 2,3ํŠœ๋ธŒ๋กœ ์ด๋™ ๊ฐ€๋Šฅ (  1๋ฒˆ ์ด๋™ )

2๋ฒˆ ์—ญ -> 1๋ฒˆํŠœ๋ธŒ๋Š” ์ด๋ฏธ ๋ฐฉ๋ฌธํ–ˆ์œผ๋‹ˆ continue

3๋ฒˆ์—ญ ->  3๋ฒˆ ํŠœ๋ธŒ๋กœ ์ด๋™ ๊ฐ€๋Šฅ ( 2๋ฒˆ ์ด๋™ )

 

3๋ฒˆ ํŠœ๋ธŒ -> 3, 6, 7๋ฒˆ ์—ญ์œผ๋กœ ์ด๋™ ๊ฐ€๋Šฅ

3๋ฒˆ ์—ญ -> ์ด๋ฏธ ๋ฐฉ๋ฌธ ํ–ˆ์œผ๋‹ˆ continue

6๋ฒˆ ์—ญ -> 4, 5 ํŠœ๋ธŒ๋กœ ์ด๋™ ๊ฐ€๋Šฅ ( 3๋ฒˆ ์ด๋™ )

5๋ฒˆ ํŠœ๋ธŒ์— N์˜๊ฐ’ 9๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ  ( 4๋ฒˆ ์ด๋™ ) 4๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

 

[์ฝ”๋“œ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Station implements Comparable<Station>{
    int index;
    int sum;
    public Station(int index, int sum) {
        this.index = index;
        this.sum = sum;
    }

    @Override
    public int compareTo(Station o) {
        return this.sum - o.sum;
    }
}

public class Main {
    public static int N; // ์—ญ์˜ ๊ฐœ์ˆ˜
    public static int K; // ํ•œ ํ•˜์ดํผํŠœ๋ธŒ๊ฐ€ ์—ฐ๊ฒฐํ•˜๋Š” ์—ญ์˜ ๊ฐœ์ˆ˜
    public static int M; // ํ•˜์ดํผํŠœ๋ธŒ์˜ ๊ฐœ์ˆ˜
    public static ArrayList<ArrayList<Integer>> tubeOut = new ArrayList<>(); // ๊ฐ ํŠœ๋ธŒ๊ฐ€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์—ญ ์ €์žฅ
    public static ArrayList<ArrayList<Integer>> tubeIn = new ArrayList<>(); // ๊ฐ ์—ญ์ด ๊ฐˆ ์ˆ˜์žˆ๋Š” ํŠœ๋ธŒ ์ €์žฅ
    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());
        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<=N;i++) {
            tubeIn.add(new ArrayList<Integer>());
        }

        tubeOut.add(new ArrayList<Integer>());
        for(int i=1;i<=M;i++) {
            tubeOut.add(new ArrayList<Integer>());
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<K;j++) {
                int num = Integer.parseInt(st.nextToken());
                tubeOut.get(i).add(num);
                tubeIn.get(num).add(i);
            }
        }
        findStation();
    }
    public static void findStation() {
        if(N == 1) {
            System.out.println(1);
            return;
        }
        
        PriorityQueue<Station> pq = new PriorityQueue<>();
        pq.offer(new Station(1, 1));

        boolean[] visitTube = new boolean[M + 1];
        boolean[] visitStation = new boolean[N + 1];

        while(!pq.isEmpty()) {
            Station p = pq.poll();
            visitStation[p.index] = true;
            for(Integer tube:tubeIn.get(p.index)) {
                if(visitTube[tube]) {
                    continue;
                }
                visitTube[tube] = true;
                for(Integer station:tubeOut.get(tube)) {
                    if(!visitStation[station]) {
                        visitStation[station] = true;
                        if(station == N) {
                            System.out.println(p.sum + 1);
                            return;
                        }
                        pq.offer(new Station(station, p.sum + 1));
                    }
                }
            }
        }
        System.out.println(-1);
    }
}