[BaekJoon] 16724 피리 부는 사나이 (Java)

1.  문제 링크

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

2.  문제

요약

• 성우가 피리를 불 때면 영과일 회원들은 성우가 정해놓은 방향대로 움직이는데, 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 합니다.
• 재훈이는 특정 지점에 'SAFE ZONE'이라는 방음 시설을 만들어 성우의 피리 소리를 듣지 못하게 하려고 합니다.
• 재훈이는 성우가 설정해놓은 방향을 분석해서 최소 개수의 'SAFE ZONE'을 만들려 합니다.
• 성우가 설정한 방향 지도가 주어졌을 때, 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 'SAFE ZONE'에 들어갈 수 있게 하는 'SAFE ZONE'의 최소 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 지도의 행의 수 N과 열의 수 M이 주어지고 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어집니다. 지도 밖으로 나가는 방향의 입력은 주어지지 않습니다.
• 출력: 첫 번째 줄에 'SAFE ZONE'의 최소 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static char[][] map;
    static int[] parents;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new char[N][M];
        parents = new int[N * 1000];

        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < M; col++) {
                map[row][col] = info.charAt(col);
                parents[row * 1000 + col] = row * 1000 + col;
            }
        }
    }

    static void solution() {
        boolean[][] visited = new boolean[N][M];
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++) {
                if(!visited[row][col]) {
                    visited[row][col] = true;
                    dfs(row * 1000 + col, visited);
                }
            }
        }

        HashSet<Integer> set = new HashSet<>();
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++)
                set.add(findParent(row * 1000 + col));
        }

        System.out.println(set.size());
    }

    static void dfs(int loc, boolean[][] visited) {
        int row = loc / 1000, col = loc % 1000;

        if(map[row][col] == 'U') row--;
        else if(map[row][col] == 'D') row++;
        else if(map[row][col] == 'L') col--;
        else if(map[row][col] == 'R') col++;

        if(isInMap(row, col)) {
            union(loc, row * 1000 + col);
            if(!visited[row][col]) {
                visited[row][col] = true;
                dfs(row * 1000 + col, visited);
            }
        }
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < N && y >= 0 && y < M) return true;
        return false;
    }

    static int findParent(int loc) {
        if(parents[loc] == loc) return loc;
        return parents[loc] = findParent(parents[loc]);
    }

    static void union(int loc1, int loc2) {
        int parent1 = findParent(loc1), parent2 = findParent(loc2);

        if(parent1 != parent2) {
            if(parent1 < parent2) parents[parent2] = parent1;
            else parents[parent1] = parent2;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}

4.  접근

• 주어진 지도의 각 지점들을 순회하면서 아직 어느 경로에도 속하지 않은 지점들에 대해 DFS를 수행하며 연결되어 있는 경로들을 찾습니다.
  • 각 지점은 행과 열의 조합으로 나타내는데, 행과 열의 최대 길이가 1000이기 때문에 각 행과 열은 0부터 999 사이의 인덱스를 가질 수 있어, (행 * 1000 + 열)을 통해 각 지점을 표현합니다.
  • 각 지점에 해당하는 방향으로 이동한 후에 이동한 지점이 지도 내에 있다면 이동한 지점과 이동 전 지점을 하나의 경로로 묶습니다.
    • 이 때, Union Find 알고리즘을 이용하여 더 작은 번호가 부모가 되도록 합니다.
  • 그리고 이동한 지점이 아직 방문되지 않았다면 DFS를 통해 해당 경로에 다른 지점들을 찾습니다.
• 위 작업을 통해 모든 경로들을 구하고 나면 parents 배열에 자신이 속한 경로의 최상위 부모가 저장되어 있을 것입니다.
• parents 배열에 있는 수들을 중복 제거합니다.
  • 중복 제거를 하고 남은 수들은 각 경로에서 대표되는 값들이 될 것이고, 이는 영과일 회원들이 지도 어느 구역에 있더라도 갈 수 있는 지점이 되게 됩니다.
  • 그러므로 이 수의 개수가 문제의 답이 됩니다.