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

문제 링크 : https://www.acmicpc.net/problem/16724

이 문제는 유니온 파인드와 dfs를 이용하여 풀 수 있습니다.

문제에서 요구하는 SAFE ZONE은 결국 사이클의 개수가 됩니다. 왜냐하면 각 위치에서 사람들이 이동하는 방향은 정해져있기 때문에 하나의 사이클 중 한 군데를 막으면 사이클 내의 모든 사람들이 접근할 수 있기 때문입니다.

이를 구현하기 위해 dfs와 유니온 파인드를 사용했습니다. 부모 배열의 경우 ixM+j의 형태로 좌측 상단부터 우측 하단 방향으로 0부터 1씩 증가하는 식으로 아이디를 부여했습니다. 이후 방문하지 않은 위치를 하나씩 dfs 탐색하여 그래프에 주어진 방향대로 이동시킵니다. 이 때 유니온 연산을 진행하여 이동 가능한 노드끼리 부모 배열을 같에 맞춰줍니다. 여기서 이미 방문한 노드에 도착했을 때 부모 배열값이 같다면 같은 사이클로 간주하여 카운트를 증가시켜줍니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static Map<Character,Integer> dy = new HashMap<>(), dx = new HashMap<>();
    static char[][] graph;
    static int[][] parent;
    static boolean[][] check;
    static int res = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new char[N][M];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++) graph[i][j] = str.charAt(j);
        }

        parent = new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                parent[i][j] = i*M+j;
            }
        }

        dy.put('D',1);
        dy.put('U',-1);
        dy.put('L',0);
        dy.put('R',0);

        dx.put('D',0);
        dx.put('U',0);
        dx.put('L',-1);
        dx.put('R',1);

        check = new boolean[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(!check[i][j]) dfs(i,j);
            }
        }

        System.out.println(res);
    }

    static void dfs(int y, int x){
        check[y][x] = true;

        int ny = y + dy.get(graph[y][x]);
        int nx = x + dx.get(graph[y][x]);
        if(ny<0 || ny>=N || nx<0 || nx>=M) return;

        if(!check[ny][nx]){
            union(y,x,ny,nx);
            dfs(ny,nx);
        }
        else{
            if(parent[y][x] == parent[ny][nx]) res++;
        }
    }

    static void union(int sy, int sx, int ey, int ex){
        int s = find(sy,sx);
        int e = find(ey,ex);

        if(s!=e) parent[ey][ex] = s;
    }

    static int find(int y, int x){
        if(parent[y][x] == y*M+x) return parent[y][x];
        else{
            int ny = parent[y][x]/M;
            int nx = parent[y][x]%M;
            return parent[y][x] = find(ny,nx);
        }
    }
}