P.16724 피리 부는 사나이

코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    static int n, m;
    static String[][] map;
    static int[][] visited;
    static int idx = 1;

    static public class Loc {
        int y, x;

        public Loc(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        map = new String[n][m];
        for (int i = 0; i < n; i++) map[i] = br.readLine().split("");
        visited = new int[n][m];

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] == 0) {
                    if (bfs(i, j)) cnt++;
                    idx++;
                }
            }
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    private static boolean bfs(int y, int x) {
        LinkedList<Loc> queue = new LinkedList<>();
        queue.add(new Loc(y, x));

        while (!queue.isEmpty()) {
            Loc poll = queue.poll();

            if (visited[poll.y][poll.x] == 0) {
                visited[poll.y][poll.x] = idx;

                if (map[poll.y][poll.x].equals("L")) queue.add(new Loc(poll.y, poll.x - 1));
                else if (map[poll.y][poll.x].equals("R")) queue.add(new Loc(poll.y, poll.x + 1));
                else if (map[poll.y][poll.x].equals("U")) queue.add(new Loc(poll.y - 1, poll.x));
                else queue.add(new Loc(poll.y + 1, poll.x));
            }
            else if (visited[poll.y][poll.x] != idx) return false;
        }

        return true;
    }
}

코드 설명

bfs 문제이다.

만들어지는 구역의 개수 = SAFE ZONE의 개수이므로 구역의 개수를 세어주면 된다.

 

조심해야할 것은 어디에서 bfs를 시작하냐에 따라서 구역이 여러 개가 될 수도 있다.

즉, 같은 구역이지만 특정 방향으로만 이동해야하기 때문에 두번 혹은 세번으로 나뉘어 세어질 수 있는 것이다.

그래서 구역마다 인덱스를 두었다.

 

0은 아예 방문하지 않은 구역이며,

그 이상은 방문한 구역의 인덱스가 된다.

 

이 때, 방문하지 않은 구역은 평소처럼 bfs를 돌려주면 되고

방문을 했는데 인덱스가 현재 인덱스가 아닌 구역은 SAFE ZONE의 개수를 증가시키지 않으면 된다.

if (visited[i][j] == 0) {
    if (bfs(i, j)) cnt++;
    idx++;
}

//bfs 내부

while (!queue.isEmpty()) {
    Loc poll = queue.poll();

    if (visited[poll.y][poll.x] == 0) {
        //logic
    }
    else if (visited[poll.y][poll.x] != idx) return false;
}

return true;