BOJ_16724_피리 부는 사나이_java

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

16724번: 피리 부는 사나이

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

/**
 백준 16724번 피리 부는 사나이
 골드 3
 */
public class BOJ_16724_피리부는사나이 {
    private static int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 하 좌 우

    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()); // 가로
        char map[][] = new char[N][M];
        for (int i = 0; i<N; i++){
            String mapInput = br.readLine();
            for (int j = 0; j<M; j++){
                map[i][j] = mapInput.charAt(j);
            }
        }

        int ans = solution(N, M, map);
        System.out.println(ans);
    }

    public static int solution(int N, int M, char[][] map){
        int[][] visited = new int[N][M]; // 방문 체크 및 연결 확인
        int cnt = 1;
        for (int i = 0; i<N; i++){
            for (int j = 0; j<M; j++){
                if (visited[i][j] == 0){ // 방문한 곳은 가지치기
                    int res = dfs(i, j, cnt, N, M, map, visited); // dfs로 영역 탐색
                    if (res == cnt){ // dfs 결과와 cnt가 같은 경우 이전 연결과 연결 없음
                        cnt++; // 새로운 연결 시작
                    }
                }
            }
        }

        return cnt -1; // cnt의 시작이 1이므로 1빼기
    }

    public static int dfs(int y, int x, int cnt,int N, int M, char[][] map, int[][] visited){
        if (visited[y][x] != 0){ // 이미 방문한 경우 종료
            return visited[y][x];
        }
        int direction = moveDirection(map[y][x]);
        int nexty = y+delta[direction][0];
        int nextx = x+delta[direction][1];
        if (isValidBoundary(nexty, nextx, N, M)){
            visited[y][x] = cnt; // 방문 체크
            visited[y][x] = dfs(nexty, nextx, cnt, N, M, map, visited); // 이전 영역와 병합되는 경우 병합
        }

        return visited[y][x];
    }

    public static int moveDirection(char direction){ // delta의 이동 방향 매칭
        switch (direction){
            case 'U':
                return 0;
            case 'D':
                return 1;
            case 'L':
                return 2;
            case 'R':
                return 3;
            default:
                return -1;
        }
    }

    public static boolean isValidBoundary(int y, int x, int height, int width){ // 범위 체크
        if (0<=y && y<height && 0<=x && x<width)
            return true;
        else
            return false;
    }

    public static void drawMap(int N, int M, char[][] map){
        for (int i = 0; i<N; i++){
            for (int j = 0; j<M; j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    public static void drawMap(int N, int M, int[][] map){
        for (int i = 0; i<N; i++){
            for (int j = 0; j<M; j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

}