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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16724번: 피리 부는 사나이

---

2. 내가 푼 방법

나는 SAFE ZONE을 루프로 정의했다. 결국 SAFE ZONE이 수렴해야 하는 특정한 위치이기 때문에, 최소의 SAFE ZONE은 최소 루프 개수를 의미한다.

 

루프는 두 개의 boolean[][] 배열을 통해 확인할 수 있다. 이전에 만들어진 적 있는 루프에 속하는지 확인하기 위한 loop 배열과 현재 움직이는 위치를 저장해둔 visit 배열을 사용했다. 다음에 이동할 위치가 루프(loop[nx][ny] == true)라면 이동을 멈추고, 아닐 경우에는 현재까지 움직였던 위치로 돌아올 경우(visit[nx][ny] == true) 최소 루프 개수를 카운팅 한 후 이동을 멈춘다. 이 두 상황이 아닐 경우에만 다음 위치로 이동할 수 있으며, 이동이 끝나면 이동 위치 초기화와 루프 생성을 설정해주면서 빠져나오면 된다.

public static void dfs(int x, int y) {
    int nx = x + dx[arr[x][y]];
    int ny = y + dy[arr[x][y]];

    if (loop[nx][ny]) return;
    if (visit[nx][ny]) {
        result++;
        return;
    }

    visit[nx][ny] = true;

    dfs(nx, ny);

    visit[nx][ny] = false;
    loop[nx][ny] = true;
}

public static void output() throws IOException {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    bw.write(result+"");

    bw.flush();
    bw.close();
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16724.java

import java.util.*;
import java.io.*;

class Main {
    static int N, M;
    static Integer[][] arr;
    static boolean[][] loop;
    static boolean[][] visit;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        // 루프 찾기
        // 이전에 찾았던 루프인지, 혹은 새로운 루프인지 고려하기
        // 새로운 루프일 경우 최소 safe zone 개수 카운팅

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!loop[i][j]) {
                    visit[i][j] = true;
                    dfs(i, j);
                    visit[i][j] = false;
                    loop[i][j] = true;
                }
            }
        }
    }

    public static void dfs(int x, int y) {
        int nx = x + dx[arr[x][y]];
        int ny = y + dy[arr[x][y]];

        if (loop[nx][ny]) return;
        if (visit[nx][ny]) {
            result++;
            return;
        }

        visit[nx][ny] = true;

        dfs(nx, ny);

        visit[nx][ny] = false;
        loop[nx][ny] = true;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new Integer[N][M];
        loop = new boolean[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                char c = line.charAt(j);

                if (c == 'D') arr[i][j] = 2;
                else if (c == 'R') arr[i][j] = 3;
                else if (c == 'L') arr[i][j] = 1;
                else arr[i][j] = 0;
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

유사한 문제를 풀어봤어서 그런지 루프를 찾는 문제라고 빠르게 인식할 수 있었다. 요즘 코드를 작성하기 전에 어떻게 어떻게 구현할지 먼저 적고 시작하는데, 덕분에 생각 정리가 빨라지고 실수를 덜 하는 것 같다.ㅎㅎ