[백준]16724번. 피리 부는 사나이

16724번: 피리 부는 사나이

앞서 풀었던 LeetCode 207. 코스스케줄 문제와 비슷한 유형으로 찾아본 문제다

문제 이해

(00:23)

• 방향
  • U : 위
  • D : 아래
  • L : 왼쪽
  • R : 오른쪽
• 최소 개수의 safe zone을 만드려고 한다.
• 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

즉 계속해서 움직이는 상황을 방지하기 위해 Safe zone을 만드는 것이다.

계속해서 움직이는 상황이라는 것은 cycle과도 같다.

cycle을 이루는 경로 중 하나라도 safe zone으로 만든다면 → cycle을 돌지 않게 된다.

문제 풀이

이미 한 번 cycle을 돌고, cycle에 속하는 노드 중 하나를 “재방문” 하는 경우

• 해당 노드는 방문은 된 적 있고
• 해당 노드를 방문했던, dfs 함수는 아직 호출이 종료되지 않았다.
  • 해당 노드를 safe zone으로 만들고
  • finish[cur] 을 true로 한 후 return 한다.
  • 그렇다면, cycle에 속하는 모든 노드들로 재귀적으로 back 하게 되기에 결국은 cycle에 존재하는 경로중 하나의 노드에 대해서만 safe zone을 만들게 된다.
• 그러니 최소의 safe zone을 만드는 것이 가능하다.

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static int n,m;
    public static final int INIT_LEN = 1000;
    public static char[][] board = new char[INIT_LEN][INIT_LEN];
    public static boolean[][] finish = new boolean[INIT_LEN][INIT_LEN];
    public static boolean[][] visit = new boolean[INIT_LEN][INIT_LEN];
    public static Map<Character,int[]> dirs = new HashMap<>();
    public static int cycle = 0;

    public static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        String line = null;
        // init board
        for(int r = 0 ; r<n;r++) {
            line = br.readLine();
            for(int c = 0 ; c < m ; c++){
                board[r][c] = line.charAt(c);
            }
        }
        // init directions
        dirs.put('D',new int[]{1,0});
        dirs.put('U',new int[]{-1,0});
        dirs.put('L',new int[]{0,-1});
        dirs.put('R',new int[]{0,1});

    }

    public static void solve(){
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                dfs(r,c);
            }
        }
    }
    public static void dfs(int r, int c){
        // 방문한 적 있는가?
        if(visit[r][c]){
            if(!finish[r][c]) cycle++;
            return;
        }
        visit[r][c] = true;

        // 다음 방문 : dirs.get(board[r][c]) 의 방향대로..
        int[] dir = dirs.get(board[r][c]);
        dfs(r+dir[0],c+dir[1]);

        // 방문 종료
        finish[r][c] = true;

    }

    public static void main(String[] args) throws IOException{
        setting();
        solve();
        System.out.println(cycle);

    }
}