[백준]16724: 피리 부는 사나이(java)

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

16724번: 피리 부는 사나이

문제

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

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

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

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

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

예제 입력 1 

3 4
DLLL
DRLU
RRRU

예제 출력 1 

2

다음과 같이 'SAFE ZONE'을 만들면 영과일 회원들이 지도 어느 구역에 있더라도 'SAFE ZONE'에 들어갈 수 있다.

 

---

풀이

같은 Cycle당 1부터 번호를 하나씩 부여한다. 그럼최종적으로 Cycle당 하나의 SAFE ZONE을 만들면 된다.

주의해야할 케이스가 있습니다.

RRRRD

UUUUD

LLLLL

이런 케이스라면 우리는 0,0의 R을 갔을 때 RRRRD > DL > LLLL > U로 cycle임을 알 수 있지만

사실 (1, 1) (1, 2) (1, 3)의 U들도 같은 cycle이 될 수 있다.

그래서 이미 cycle로 구성됐는지 확인하는 isGroup함수를 먼저 사용해주었다.

public static void isGroup(int x, int y) {
    if(cycle[x][y] != 0) {
        num = cycle[x][y];
        return;
    }
    if(visited[x][y]) {
        return;
    }
    visited[x][y] = true;
    int d = getDist(map[x][y]);
    isGroup(x + dist[d][0], y + dist[d][1]);
}

visited를 통해 중복이 되지 않게 돌면서 만약 cycle에 체크된 곳으로 흘러가게되면 그 cycle의 num을 반환해준다.

 

num = 0;
isGroup(i, j);
if(num!=0) {
    findGroup(i, j, num);
} else {
    findGroup(i, j, groupNum);
    groupNum++;
}

따라서 num이 0으로 반환된다 = 새로운 그룹을 만들어줘야하는 케이스

num이 0이 아니다. 이미 num으로 이루어진 cycle에 포함되어야하는 케이스로 분류될 수 있다.

group번호를 cycle배열에 넣어주는 함수는 findGroup함수이다.

public static void findGroup(int x, int y, int groupNum) {
    if(cycle[x][y] != 0) {
        return;
    }
    cycle[x][y] = groupNum;
    int d = getDist(map[x][y]);
    findGroup(x + dist[d][0], y + dist[d][1], groupNum);
}

전체 코드

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

public class BJ_G2_16724_피리부는사나이 {
    static int N, M;
    static char[][] map;
    static int[][] cycle;
    static boolean[][] visited;
    static int[][] dist = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int num;
    public static void main(String[] args) throws Exception{
        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];
        cycle = new int[N][M];
        visited = new boolean[N][M];
        int groupNum = 1;

        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(cycle[i][j] != 0) continue;
                num = 0;
                isGroup(i, j);
                if(num!=0) {
                    findGroup(i, j, num);
                } else {
                    findGroup(i, j, groupNum);
                    groupNum++;
                }
            }
        }
        System.out.printf("%d", groupNum-1);
    }

    public static void isGroup(int x, int y) {
        if(cycle[x][y] != 0) {
            num = cycle[x][y];
            return;
        }
        if(visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        int d = getDist(map[x][y]);
        isGroup(x + dist[d][0], y + dist[d][1]);
    }

    public static void findGroup(int x, int y, int groupNum) {
        if(cycle[x][y] != 0) {
            return;
        }
        cycle[x][y] = groupNum;
        int d = getDist(map[x][y]);
        findGroup(x + dist[d][0], y + dist[d][1], groupNum);
    }

    public static int getDist(char d) {
        switch(d) {
            case 'U':
                return 0;
            case 'R':
                return 1;
            case 'D':
                return 2;
            case 'L':
                return 3;
        }
        return 0;
    }
}