[자바] 백준 3197 - 백조의 호수 (java)

 문제 : boj3197

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs)
  
  • 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다.
• 분리 집합 (disjoint set)
  
  • 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다.

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

 

---

 

풀이

  혹시 BFS에 대해 잘 모른다면 이 글을 먼저 읽어보자. 우선 주의점은 L로 써져 있는 곳도 물인 공간이다. 그리고 이후 모든 물에서부터 (좀 더 최적화 하겠다면 빙판과 접촉되어 있는 물부터) 기본적인 형태의 BFS를 진행하면 된다. 이 때 문제가 되는 것은, 백조가 서로 만났는지 확인하기 위해 매번 BFS 혹은 DFS를 통해 만날 수 있는 판단하면 시간초과가 나게 된다는 점이다.

 

  이걸 해결하기 위해 분리 집합을 사용하면 된다. 유니온 파인드 알고리즘을 통해 매번 인접한 물에 대해 그룹을 만들어주게 되면 두 오리의 분리되어 있던 집합이 동일한 그룹에 포함되는 것을 확인해서 만날 수 있는지 판단할 수 있다.

 

 

---

 

코드 : github

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

public class Main {
    private int C;
    private int[] parents;
    private int[] swan = new int[2];
    private static final int[] DR = {1, -1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        int h = parents[a]<parents[b]?a:b;
        int l = parents[a]<parents[b]?b:a;
        parents[h]+=parents[l];
        parents[l] = h;
    }

    private int rcToIdx(int r, int c) { return r*C+c; }
    private boolean isSwanMeet() { return find(swan[0]) == find(swan[1]); }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = C = Integer.parseInt(st.nextToken());
        parents = new int[r*c];
        Arrays.fill(parents, -1);
        int[][] map = new int[r][c];
        for (int i = 0; i < r; i++) Arrays.fill(map[i], -1);
        int swanIdx = 0;
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                char ch = row.charAt(j);
                switch (ch) {
                    case 'L': swan[swanIdx++] = rcToIdx(i,j);
                    case '.': map[i][j] = 0; break;
                }
            }
        }

        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) continue;
                boolean isQueueCandidate = false;
                for (int d = 0; d < 4; d++) {
                    int nr = i + DR[d];
                    int nc = j + DC[d];
                    if (nr<0||nr>=r||nc<0||nc>=c) continue;
                    if (map[nr][nc] != -1) union(rcToIdx(i,j), rcToIdx(nr,nc));
                    else isQueueCandidate = true;
                }
                if (isQueueCandidate)
                    q.add(new int[]{i,j,0});
            }
        }

        if (isSwanMeet()) {
            System.out.println(0);
            return;
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            int dist = cur[2];
            for (int d = 0; d < 4; d++) {
                int nr = cr + DR[d];
                int nc = cc + DC[d];
                if (nr<0||nr>=r||nc<0||nc>=c) continue;
                union(rcToIdx(cr,cc), rcToIdx(nr,nc));

                if (isSwanMeet()) {
                    System.out.println(map[nr][nc]);
                    return;
                }

                if (map[nr][nc] != -1) continue;
                map[nr][nc] = dist+1;
                q.add(new int[]{nr,nc,dist+1});
            }
        }
    }

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