[자바] 백준 5214 - 환승 (java)

 문제 : boj5214

---

 

필요 알고리즘 개념

• BFS (너비 우선 탐색)
  
  • 너비 우선 탐색 문제이다. 다만 간선 설정이 어려운걸 끼얹은..

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

그냥 생각해보기

  문제 자체는 정점과 간선이 주어지고 그냥 BFS를 돌리면 되는 간단한 문제이다. 다만 이 간선이 한번에 K개씩 주어진다는게 문제이다. 즉, 로직 자체는 BFS면 되지만 간선을 어떻게 저장해둘지가 핵심인 문제이다. BFS를 모른다면 이 글을 참고하자.

 

  우선 일반적으로 하던 것 처럼 간선을 설정하는걸 생각해보자. M개의 간선 정보에 대해 K개의 정점들이 주어진다. 그럼 K*K번 반복하면서 서로서로 간선을 연결하면 된다. 예를들어서 '1 2 3' 이라고 하면, 2중 반복문으로 모든 경우인 1-2, 2-3, 1-3에 대해 간선을 연결해주면 된다. 

 

  예제 입력1을 생각해보자.

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

위 예시에 대해 위에서 말한대로 입력을 받으면서 한땀한땀 정점들을 모두 연결해준다면 아래와 같다.

 

 

  다만 위와 같이 할 경우 간선 입력받는데만 O(MK^2)이 필요하므로 이미 입력받는 동안 시간초과가 날 것이다.

 

---

 

풀이 1

  풀이1은 내가 처음에 생각했던 풀이 방식이다. 객체지향적으로 생각해서 진행한 것이고, 풀이2는 이 문제를 풀기 위해 일반적으로 알려진 웰-논한 방식이다. 효율성은 둘 다 동일하다. 사람마다 차이는 있겠지만, 코드 구현적으로 풀이2쪽이 좀 더 짜기 편할 것 같다.

 

  M개의 하이퍼튜브 정보들을 따로 객체로 생각한다. 그리고 각 하이퍼튜브 객체에 들어있는 K개의 정점들에서, 해당 하이퍼튜브로 간선을 연결해줄꺼다(정확힌 그냥 간선 정보를 얻기 위한 객체 포인터다.). 이후 BFS를 진행하면서 연관된 하이퍼튜브들을 가져오고, 각 하이퍼튜브를 통해 간선정보를 얻어 진행할꺼다. 개념적으로 그려보면 다음과 같다.

 

  이 경우, K개를 입력받으면서 객체를 하나 만들어주고 (아래 그림의 한 행에 해당), 해당 객체 내의 모든 정점에서 간선을 연결해준다. 따라서 O(K+K)로 입력받는게 가능하다. 코드로 입력과정을 나타내면 다음과 같다. 다만 이하 전체 코드를 보면 tmp를 k+1개로 생성하고 tmp[0] = m 으로 해두었다. 이건 0번 인덱스를 하이퍼튜브 객체 방문체크로 쓰기 위해 설정한 것이다. 부가적인 부분이므로 개념적으론 이하의 코드로 생각하면 된다.

while (m-->0) {	// m개를 입력받음
    st = new StringTokenizer(br.readLine());
    int[] tmp = new int[k];	
    for (int i = 0; i < k; i++) 
    	tmp[i] = Integer.parseInt(st.nextToken()); // 각 하이퍼튜브의 정점 k개를 입력받음
    for (int i = 0; i < k; i++) 
    	edges[tmp[i]].add(tmp);	// 하이퍼튜브의 각 정점에서 하이퍼튜브로 간선을 연결
}

 

  bfs 탐색 방법은 다음과 같다. 항상 정점에서 하이퍼튜브 객체로 이동하고(방문 체크1), 하이퍼튜브 객체에서 다른 정점으로 이동한다(방문 체크2). 개념적으로 정점과 하이퍼튜브 객체는 서로 다른 것으로 보고 있으므로, 방문 체크를 별도로 해줘야 한다. 풀이2에서는 하이퍼튜브 객체도 일종의 정점으로 보는 방식이다.

ArrayList<int[]> edgesList = edges[cur[0]];
for (int i = 0; i < edgesList.size(); i++) {	// 해당 정점과 연관된 하이퍼튜브 객체 순회
    int[] edge = edgesList.get(i);
    if (edgeV.contains(edge[0])) continue;	// 하이퍼튜브 방문체크1
    edgeV.add(edge[0]);
    for (int j = 1; j <= k; j++) {
        int next = edge[j];	// 해당 하이퍼튜브에서 진행 가능한 정점들
        if (v[next]) continue; // 방문체크2
        v[next] = true;
        q.add(new int[]{next, cur[1] + 1});
    }
}

 

  정점이 있고, 간선정보도 모두 있다면 이제 BFS를 돌리는건 위에서 링크해뒀던 BFS 글만 이해해도 어렵지 않게 할 수 있다. 내 경우엔 메모리 복잡도를 낮추고자 int[] 형태로 큐나 하이퍼튜브 객체를 유지했지만, 객체로 만들면 더 객체지향적으로 짤 수 있을 것이다.

 

코드 (풀이1) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<17);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<int[]>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int[] tmp = new int[k+1];
            tmp[0] = m;
            for (int i = 1; i <= k; i++) tmp[i] = Integer.parseInt(st.nextToken());
            for (int i = 1; i <= k; i++) edges[tmp[i]].add(tmp);
        }
        boolean[] v = new boolean[n+1];
        HashSet<Integer> edgeV = new HashSet<>();
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1,1});
        v[1] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n) {
                System.out.println(cur[1]);
                return;
            }
            ArrayList<int[]> edgesList = edges[cur[0]];
            for (int i = 0; i < edgesList.size(); i++) {
                int[] edge = edgesList.get(i);
                if (edgeV.contains(edge[0])) continue;
                edgeV.add(edge[0]);
                for (int j = 1; j <= k; j++) {
                    int next = edge[j];
                    if (v[next]) continue;
                    v[next] = true;
                    q.add(new int[]{next, cur[1] + 1});
                }
            }
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

---

 

풀이2

  이 문제처럼 간선 정보가 한번에 여러개가 입력된 경우에 흔히들 말하는 웰-논(...)한 방법이 있다. 위에선 하이퍼튜브와 정점을 다른 것으로 봤지만, 이번엔 하이퍼튜브를 그냥 하나의 더미 정점으로 보는거다. 개념은 풀이1과 동일하다. 그림으로 그려야 아마 이해가 갈 것이다. 마찬가지로 예제 입력 1을 계속 보자.

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

 

  이걸 그려보면 아래와 같다. M1, M2,... 들이 M개의 입력값에 대한 더미 정점이다.

 

  그럼 새로 생긴 더미 정점들도 그냥 원래 있던 정점으로 치고 BFS를 돌려주면 답을 구할 수 있게 된다. 입력과정을 코드로 보면 다음과 같다. 풀이1과 달리 bfs를 진행 시 하이퍼튜브 객체들도 동일선상에서 정점으로 보고 순회 가능하므로 좀 더 코드가 간소해진다. 다만 이 경우 더미 정점에서는 순회 횟수를 증가시키면 안되니 이 부분은 주의해야 한다. (코드에서 next>n?cur[1]:cur[1]+1})

ArrayList<Integer>[] edges = new ArrayList[n+1+m];	// m개의 더미 정점이 더 생길 것이므로 n+1+m개가 된다.

...

while (m>0) {	// 각각마다 더미 정점의 번호는 m+n으로 했다. 기존 정점과만 안겹치게 임의로 정하면 된다.
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < k; i++) {	// k개의 하이퍼튜브 정점 정보에 대해 k개정점->더미정점, 더미정점->k개정점 으로 간선 연결
        int cur = Integer.parseInt(st.nextToken());
        edges[n+m].add(cur);
        edges[cur].add(n+m);
    }
    m--;
}

 

 

 

코드 (풀이2) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<17);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] edges = new ArrayList[n+1+m];
        boolean[] v = new boolean[n+1+m];
        for (int i = 1; i <= n+m; i++) edges[i] = new ArrayList<>();
        while (m>0) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < k; i++) {
                int cur = Integer.parseInt(st.nextToken());
                edges[n+m].add(cur);
                edges[cur].add(n+m);
            }
            m--;
        }
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1,1});
        v[1] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n) {
                System.out.println(cur[1]);
                return;
            }
            for (int next : edges[cur[0]]) {
                if (v[next]) continue;
                v[next] = true;
                q.add(new int[]{next, next>n?cur[1]:cur[1]+1});
            }
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}