[백준] Q16724 피리 부는 사나이 JAVA

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

16724번: 피리 부는 사나이

1. 문제의 유형 및 이해

그래프 탐색, disjoint set

맵을 벗어나지 않고 맵에 적힌 방향으로 계속해서 움직이는 회원들을 위해 SAFEZONE을 설치하여 어느구역에 있더라도

SAFEZONE으로 들어가 더이상 움직이지 않게 하고 싶다.

SAFE ZONE의 최소 개수를 구하는 문제

 

맵을 벗어나지 않고 계속해서 움직이는 어떠한 cycle이 존재한다. cycle의 개수만큼 SAFE ZONE을 설치해주면 최소한의 개수로 설치할 수 있다.

2. 문제 접근 방법

어떠한 cycle을 체크하기 위해서 맵을 탐색하여 cycle을 탐지해야한다.

cycle은 어떤 방문한 곳을 다시 방문하게 되면 cycle이 형성이 되는데, 우리가 놓아야 하는 SAFE ZONE은 사이클을 포함한 연결된 하나의 그래프의 그룹개수가 조금 더 정확한 표현이다.

 

임의의 한 곳에서 cycle에 연결된 노드가 있다면 이 곳에서도 해당 사이클에 포함되기 때문에 이 노드들까지 포함하여 하나의 그룹을 형성해주어야 한다.

 

'그룹'임을 인지시켜주기 위해 여러가지 방법이 있는데

1. 그룹마다 번호를 붙이는 방법

방문하지 않은 노드들에서 DFS를 수행하면서 사이클인 노드들에 대해 그룹 번호를 붙여준다.

이후 어떤 임의의 노드에서 DFS를 수행하던 중 방문한 노드를 만나고 이미 그룹 번호가 있다면 해당 path도 같은 그룹에 속하도록 해주는 방법이 있다.

한 노드에 연결된 간선이 하나로 BFS보다는 DFS가 조금 더 적합하다.

 

2. Disjoint set을 이용하는 방법

노드들이 연결된 곳들을 따라 연결시켜주게 되면 하나의 그룹이 형성되게 된다.

이 때 root의 개수가 group의 개수로 정답이 된다.

 

실제 구현은 DFS로 구현하였다.

방문했던 노드를 만났는데 groupNum =0으로 아직 정해지지 않았다면 groupNum를 증가시켜주고 해당 groupNum으로 바꿔준다.

만약 방문했던 노드를 만났는데 groupNum !=0으로 group이 지어져있다면 해당 번호로 지정해준다.

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

/**
 * @문제번호 : Review_16742
 * @문제이름 : 피리 부는 사나이
 * @난이도 : Gold II
 * @date : 2022-02-26 오후 2:42
 * @author : pcrmcw0486
 * @문제이해
 * 정해진 방향으로 움직일 때 (U,D, L, R)
 * SAFEZONE에 가면 더 이상 움직이지 못하게 할대, 최소의 SAFEZONE 설치 개수
 * 어디 있더라도 들어가게 해야한다.
 * @알고리즘
 * 지도 안에서 어디든 계손해서 움직이는 cycle이 항상 존재한다.
 * cycle개수를 파악해야하는데, 조금 더 정확하게는
 * cycle과 해당 cycle에 연결된, 칸들을 '하나의 그룹'으로 묶어야 한다.
 * @접근방법
 * 신박하게 두 가지 방법이 있다.
 * 정석적으로 DFS를 통해 grouping을 하는 방법. using number
 * 또는 disjoint set을 활용해서 grouping을 하는 방법.
*/
public class Main {
    static char[][] map;
    static int[][] groupMap;
    static boolean[][] isVisited;
    static int groupNum =0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        groupMap = new int[N][M];
        isVisited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        for(int i =0;i<N;i++){
            for(int j=0;j<M;j++){
                if(!isVisited[i][j]){
                    findGroup(i, j);
                }
            }
        }
        for (int[] line : groupMap) {
            for (int c : line) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
        System.out.println("==========");
        System.out.println(groupNum);
    }

    private static void findGroup(int i, int j) {
        isVisited[i][j] = true;
        int nx =i;
        int ny = j;
        switch (map[i][j]) {
            case 'U':
                nx-=1;
                break;
            case 'R':
                ny+=1;
                break;
            case 'D':
                nx+=1;
                break;
            case 'L':
                ny-=1;
                break;
        }
        if (isVisited[nx][ny]) {
            if(groupMap[nx][ny] ==0){
                groupMap[i][j] = ++groupNum;
            }else{
                groupMap[i][j] = groupMap[nx][ny];
            }
        }else{
            findGroup(nx, ny);
            groupMap[i][j] = groupMap[nx][ny];
        }
    }

}