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

16724번: 피리 부는 사나이

---

[DFS]

주어진 방향 지도가 있을 때, (1) 사이클이 있을 때, (2) 방향을 따라가다 벽에 막히는 곳이 있을 때 'SAFE ZONE'을 설치하면 된다.

주어진 예제 입력으로 지도를 그려보자. 편의상 U = 0, D = 1, L = 2, R = 3으로 표기하겠다.

1	2	2	2
1	3	2	0
3	3	3	0

위와 같이 지도가 주어지고, 빨간색은 사이클이 존재하는 곳, 파란색도 사이클이 존재하는 곳이다. 저 두 개의 사이클 중 한 곳씩 세이프 존을 만들어주면 되므로 답은 2개가 된다. 그런데 이 예제에는 존재하지 않지만, 사이클이 없고 벽으로 가로막힌 곳(범위를 벗어나는 좌표 y, x)를 만나면 또한 벽으로 가로막힌 곳에 세이프존을 만들어주어야 한다.

 

그래서 위의 2가지 조건 중 하나를 만족하면 세이프존을 만들어주고, 그 영역을 동일한 번호로 넘버링 했다. 그래서 위의 예제를 check[ ][ ]라는 배열에서 보면 다음과 같다.

0	0	0	0
0	1	1	0
0	0	0	0

이는 0을 갖는 녀석들은 세이프존 1개만 있으면 되고, 1을 갖는 녀석들도 세이프존을 1개만 가지면 된다는 뜻으로, 총 2개가 필요한 것이다.

# Code </>

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

public class Main {

    static int r, c, cnt=0;
    static int[][] map = new int[1001][1001], check = new int[1001][1001];
    static boolean[][] visit = new boolean[1001][1001];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};

    /* 사이클 발견 : cnt++, 사이클이 아닌 벽으로 가로막힌곳, cnt++ */
    /* -1: 미방문 */
    static int DFS(int y, int x){

        if(check[y][x] != -1) return check[y][x];

        if(y < 1 || x < 1 || y > r || x > c || visit[y][x])
            return cnt++;

        visit[y][x] = true;

        int dir = map[y][x];

        int ny = y+Y[dir];
        int nx = x+X[dir];

        check[y][x] = DFS(ny, nx);

        return check[y][x];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++){
                char c = str[j-1];

                if(c == 'U') map[i][j] = 0;
                else if(c == 'D') map[i][j] = 1;
                else if(c == 'L') map[i][j] = 2;
                else map[i][j] = 3;

                check[i][j] = -1;
            }
        }

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                if(!visit[i][j])
                    DFS(i, j);

        System.out.println(cnt);
    }
}