[JAVA] BOJ 백준 5214번 - 환승

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

첨에 다른 분 풀이를 본 후 풀어서, 5일 뒤에 다시 시도해 푼 문제이다.

 

하이퍼튜브를 또 다른 정점으로 판단하여 해결하면 아주 쉬운 문제이다.

기존 정류장 정점은 1 ~ N까지, 하이퍼튜브 정점은 N+1 ~ N+M까지 설정하고, 역과 하이퍼튜브를 연결해 그래프를 만든다.

int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

List<Integer>[] list = new ArrayList[N+M+1];
for (int i = 1; i <= N+M; i++) {
    list[i] = new ArrayList<>();
}

for (int m = 1; m <= M; m++) {
    st = new StringTokenizer(br.readLine());

    int hyper = N+m;

    for (int k = 0; k < K; k++) {
        int v = Integer.parseInt(st.nextToken());

        list[v].add(hyper);
        list[hyper].add(v);
    }
}

 

이제 1부터 N까지 그래프를 이동해주면 되는데 현재 있는 노드가 정류장이면 move를 카운팅해주고, 하이퍼튜브면 move 값 그대로 가져간다.

public static int bfs (List<Integer>[] list, int N) {
    int result = -1;

    boolean[] check = new boolean[list.length];
    check[1] = true;

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(1, 1));

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int idx = tuple.idx;
        int move = tuple.move;

        if (idx == N) {
            result = move;
            break;
        }

        for (int i : list[idx]) {
            if (!check[i]) {
                check[i] = true;

                if (i > N) queue.add(new Tuple(i, move));
                else queue.add(new Tuple(i, move+1));
            }
        }
    }

    return result;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B5214.java

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer>[] list = new ArrayList[N+M+1];
        for (int i = 1; i <= N+M; i++) {
            list[i] = new ArrayList<>();
        }

        for (int m = 1; m <= M; m++) {
            st = new StringTokenizer(br.readLine());

            int hyper = N+m;

            for (int k = 0; k < K; k++) {
                int v = Integer.parseInt(st.nextToken());

                list[v].add(hyper);
                list[hyper].add(v);
            }
        }

        bw.write(bfs(list, N)+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int bfs (List<Integer>[] list, int N) {
        int result = -1;

        boolean[] check = new boolean[list.length];
        check[1] = true;

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(1, 1));

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int idx = tuple.idx;
            int move = tuple.move;

            if (idx == N) {
                result = move;
                break;
            }

            for (int i : list[idx]) {
                if (!check[i]) {
                    check[i] = true;

                    if (i > N) queue.add(new Tuple(i, move));
                    else queue.add(new Tuple(i, move+1));
                }
            }
        }

        return result;
    }

    public static class Tuple {
        int idx;
        int move;

        public Tuple (int idx, int move) {
            this.idx = idx;
            this.move = move;
        }
    }
}

 

---

4. 결과 및 회고

다시 풀어보니 쉬운 문제인데 왜 처음엔 생각을 못해냈을까.. ㅠㅠ

그래도 지금은 이런 방법도 생각해 낼 수 있으니 아자아자!