[백준/JAVA] BOJ 16724 - 피리 부는 사나이

까보면 사실은 간단한 문제?

👀 문제

16724번: 피리 부는 사나이 ✨ 골드 3

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

예제 입력

3 4
DLLL
DRLU
RRRU

예제 출력

2

🔑 키포인트

사이클 판단 그래프 탐색 깊이 우선 탐색

✍️ 코드

📍 사이클 개수를 세는 게 다인 문제였다

💡 지도 밖으로 나가는 입력도 없고, 화살표는 결국 다 연결되어 있으므로 사이클이 형성되는 부분들에 SAFE ZONE을 만들면 모든 위치에서 들어갈 수 있게 된다!

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

public class BOJ16724_피리부는사나이 {
    static int n, m, cnt;
    static char[][] map;
    static boolean[][] visited, finished;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        visited = new boolean[n][m];
        finished = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    static void dfs(int x, int y) {
        int dir = getDir(map[x][y]);
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (!visited[nx][ny]) {
            visited[nx][ny] = true;
            dfs(nx, ny);
        } else if (!finished[nx][ny]) {
            // 방문했는데 아직 안 끝났음 싸이클이다
            cnt++;
        }
        finished[x][y] = true;
    }

    static int getDir(char c) {
        switch (c) {
            case 'U':
                return 0;
            case 'D':
                return 1;
            case 'L':
                return 2;
            case 'R':
                return 3;
        }
        return -1;
    }
}