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

문제 링크: 16724번 제목

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

 

마치 섬의 개수를 세듯이, 어딘가에서 연결되어 있는 덩어리의 개수만큼만 SAFE ZONE이 있으면 된다.

임의의 점 P를 잡았을 때, 해당 P에 쓰인 화살표부터 끝까지 따라가면 이미 방문했던 어딘가가 나오게 되므로 해당 덩어리를 모두 탐색한 것이다...라고 하면 거짓말이고, P가 해당 덩어리의 '처음'이라는 보장은 없다.

 

 

위 그림에서, 하늘색 부분은 임의의 점을 택하더라도 반드시 모든 점을 순회하게 되지만,

연두색이나 연노란색 부분은 그렇지 않다.

특히 연두색의 경우 2행 2열을 먼저 확인하게 되는데, 그러면 2행 2열과 2행 3열은 다른 덩어리로 분류되어버린다.

 

따라서 이전 노드 또한 함께 확인하여 덩어리를 확인할 수 있도록 한다. 이것이 54~62라인의 내용이다.

 

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

public class Main {
    static int rows;
    static int cols;
    static char[][] map;
    static boolean[][] visit;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());
        map = new char[rows][cols];
        visit = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            String line = br.readLine();
            for (int j = 0; j < cols; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visit[i][j]) {
                    dfs(i, j);
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }

    static void dfs(int row, int col) {
        if (row<0 || col<0 || row>=rows || col>=cols) return;
        if (visit[row][col]) return;
        visit[row][col] = true;

        // check next
        if (map[row][col] == 'U')
            dfs(row-1, col);
        else if (map[row][col] == 'L')
            dfs(row, col-1);
        else if (map[row][col] == 'R')
            dfs(row, col+1);
        else if (map[row][col] == 'D')
            dfs(row+1, col);

        // check prev
        if (col+1 < cols && map[row][col+1] == 'L')
            dfs(row, col+1);
        else if (col-1 >= 0 && map[row][col-1] == 'R')
            dfs(row, col-1);
        else if (row+1 < rows && map[row+1][col] == 'U')
            dfs(row+1, col);
        else if (row-1 >= 0 && map[row-1][col] == 'D')
            dfs(row-1, col);
    }
}