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

1. 문제

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

16724번: 피리 부는 사나이

2. 접근방법

조건 중에

'지도 밖으로 나가는 방향의 입력은 주어지지 않는다.' 라는 조건이 있기 때문에

지도 안에서만 회전 하는 형태가 된다.

 

그렇다면 이동 공간 중 끝까지 가면 모이게 되는 그룹들이 형성 되는데

그 그룹만 잘 찾아내면 쉽게 해결 가능하다.

 

예전 섬의 갯수 구하기 인가 그 문제랑 비슷한 것 같다.

나는 백트레킹을 이용해서 풀이했다.

 

1. 0,0 부터 아직 체크되지 않은 지역은 출발

2. 화살표 따라 이동

3-1. 이동하다가 내가 지나온 길과 또 만나면 새로운 그룹 생성, 백트레킹으로 새로운 번호로 map에 체크

3-2. 이동하다가 0이 아닌 이미 저장된 번호의 길을 만나면 내가 지금껏 온길을 방금 만난 번호로 저장

4. 마지막으로 새롭게 추가한 번호가 정답.

 

3. 자바 코드

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

public class P16724피리부사나이 {
    static char map[][];
    static int checkMap[][];
    public static void main(String[] args) throws Exception {
        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());
        map = new char[N][M];
        checkMap = new int[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++)
                map[i] = s.toCharArray();
        }
        for(int i = 0 ; i < N ; i++)
            for(int j = 0 ; j < M ; j++)
                if(checkMap[i][j] == 0)
                    go(i,j);
        System.out.println(cnt-1);
    }
    static int cnt = 1;
    static int go(int row, int col) {
        if(checkMap[row][col] != 0){
            if(checkMap[row][col] == cnt)
                cnt++;
            return checkMap[row][col];
        }
        int nextRow = row;
        int nextCol = col;
        checkMap[row][col] = cnt;
        if(map[row][col] == 'D')  nextRow +=1;
        else if(map[row][col] == 'U') nextRow -=1;
        else if(map[row][col] == 'L') nextCol -=1;
        else if(map[row][col] == 'R') nextCol +=1;
        return checkMap[row][col] = go(nextRow,nextCol);
    }
}

4. 마치며

골드2 치고는 좀 쉬운 듯