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

백준 자바 16724 피리 부는 사나이 BFS 

16724번: 피리 부는 사나이

[문제 풀이 방법]

사이클을 따라서 방문 처리되지 않은 원소(0인 원소들) 들을 방문 처리하면서 길을 따라가다가

만약 이전에 방문했던 곳이면 사이클을 따라 safezone이 하나 있어야 하므로 safezone을 하나 증가시켜야 한다

 

하지만 만약 사이클을 따라가다가 이전에(이번 턴이 아닌) 방문처리가 된 원소라면

이미 이전 턴의 사이클에 safezone이 존재하므로 safezone을 증가시키지 않고 다음으로 지나가는 로직이 있어야 한다.

 

이을 위해서 idx를 활용해서 길을 따라간 턴 수를 저장하였다.

 

idx 이용해서 만약 이번 턴에 방문한 길에서만 사이클이 존재한다면 safezone이 하나 증가해야 하고

방문한 visited의 idx가 다르다면 이전 턴에 방문했던 노드와 겹친 경우 이므로 이미 safe zone으로 가는 길이 있어 증가시키지 않고

지나가는 방법으로 구현하여 테스트 케이스를 통과하였다.

 

 

[코드]

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

public class Main {
    private static int col = 0, row = 0;
    private static char[][] map;
    private static int[][] visited;
    private static int cnt = 0; //최소 safe zone
    private static int idx = 1; //턴을 분리하기위해서


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map = new char[row][col];
        visited = new int[row][col];

        /*input*/
        for (int i = 0; i < row; i++) {
            char[] tmp = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                map[i][j] = tmp[j];
            }
        }

        /*탐색 길 따라가면서 */
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j] == 0) {
                    bfs(i, j);
                }
            }
        }


        System.out.println(cnt);

    }

    private static void bfs(int i, int j) {
        //현재 노드 탐색 확인
        visited[i][j] = idx; 
        //이동하는 칸 
        int[] move = getNowt(map[i][j]);
        int movex = i + move[0];
        int movey = j + move[1];

        if (visited[movex][movey] == 0) {
            bfs(movex, movey); //만약 탐색 되지 않은공간 이면 계속 해서 탐색
        }
        else {
            if (visited[movex][movey] == idx) { //싸이클이 생겼는데 이번턴에서만 사이클만 있다면 safezone++
                cnt++;
            }
            idx++; // 이번턴과 다음턴을 분리하기 위해서
        }
    }

    private static int[] getNowt(char now) {
        switch (now) {
            case 'U':
                return new int[]{-1, 0};
            case 'D':
                return new int[]{1, 0};
            case 'L':
                return new int[]{0, -1};
            case 'R':
                return new int[]{0, 1};
        }
        return new int[]{00}; //ERROR
    }
}