[백준] BOJ_16724 - 피리 부는 사나이

1. 문제 분석

🕵️‍♂️ 제약 조건 파악

• 지도 크기: $N, M$은 최대 1,000입니다.
  
• 총 칸의 수: $1,000 \times 1,000 = 1,000,000$ (백만)개입니다.
  
• 시간 복잡도: 일반적인 DFS/BFS의 시간 복잡도는 $O(V+E)$입니다. 여기서는 모든 칸이 하나의 간선을 가지므로 $O(N \times M)$으로 해결 가능합니다. $N$이 작아 보이지만 2차원 배열 전체를 탐색해야 하므로, $O((NM)^2)$ 같은 비효율적인 로직은 시간 초과가 날 수 있습니다.
  

🔑 키워드 및 가설

• "방향" (U, D, L, R): 각 칸에서 갈 수 있는 곳은 오직 하나입니다. (Functional Graph 특징)
  
• "더 이상 이동할 수 없을 때까지": 결국 모든 경로는 어딘가에서 사이클(Cycle)을 형성하거나, 기존의 사이클로 합류하게 됩니다.
  
• "최소 개수": 사이클 하나당 하나의 'Safe Zone'이 필요합니다. 즉, 이 문제는 "그래프 내에 존재하는 독립적인 컴포넌트(집합)의 개수"를 구하는 것과 같습니다.
  

---

2. 알고리즘 설계

사용 알고리즘: DFS

처음에는 단순히 Union-Find를 떠올렸지만, 방향이 있는 그래프이고 사이클을 감지해야 하므로 DFS를 사용하여 방문 상태를 관리하는 것이 더 직관적이라 판단했습니다.

핵심 로직: Visited vs Finished

이 문제의 핵심은 "이미 방문한 노드를 만났을 때"의 처리입니다.

1. 모든 칸을 순회하며 방문하지 않은 곳에서 DFS를 시작합니다.

2. 이동하다가 이미 방문한 칸(visited == true)을 만났을 때 두 가지 경우가 있습니다.

   • Case A: 이번 탐색에서 방문한 칸을 다시 만남 $\rightarrow$ 새로운 사이클 발견! (정답 +1)
     
   • Case B: 이전의 다른 탐색에서 이미 처리가 끝난 칸(cycle == true)을 만남 $\rightarrow$ 기존 집합에 합류하는 경로임. (정답 증가 X)
     

3. 이 두 가지를 구분하기 위해 방문 배열(visit) 외에 탐색 완료 배열(cycle)이 하나 더 필요합니다.

시간 복잡도

• 모든 정점($N \times M$)을 한 번씩만 방문하므로 $O(N \times M)$입니다. 제한 시간 내에 충분히 통과 가능합니다.
  

---

3. 코드 구현

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static char[][] A;
    static boolean[][] visit; // 방문 여부 체크
    static boolean[][] finished; // 사이클(탐색) 완료 여부 체크
    static int answer = 0;

    // 방향 처리를 위한 배열 (U, D, L, R)
    static final int[] dy = {-1, 1, 0, 0};
    static final int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        // 1. 입력 처리
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new char[N][M];

        for (int i = 0; i < N; i++) {
            A[i] = br.readLine().toCharArray();
        }

        visit = new boolean[N][M];
        finished = new boolean[N][M];

        // 2. 전체 맵을 순회하며 DFS 수행
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visit[i][j]) {
                    dfs(i, j);
                }
            }
        }

        System.out.println(answer);
    }

    private static void dfs(int y, int x) {
        visit[y][x] = true; // 현재 노드 방문 처리

        int d = dir(A[y][x]);
        int ny = y + dy[d];
        int nx = x + dx[d];

        // 다음 노드를 아직 방문하지 않았다면 계속 탐색
        if (!visit[ny][nx]) {
            dfs(ny, nx);
        } 
        // 다음 노드를 방문은 했지만, 아직 탐색 처리가 끝나지 않았다면? 
        // -> 이번 탐색 경로에서 만난 것이므로 '사이클'이다!
        else if (!finished[ny][nx]) {
            answer++;
        }

        // 현재 노드의 탐색 종료 처리 (이후 다른 경로에서 이 노드를 만나면 사이클이 아님)
        finished[y][x] = true;
    }

    // 문자를 방향 인덱스로 변환하는 헬퍼 메서드
    private static int dir(Character c) {
        if (c == 'U') return 0;
        if (c == 'D') return 1;
        if (c == 'L') return 2;
        return 3;
    }
}

---

4. 회고 및 배운점

💡 핵심 포인트

이 문제의 승부처는 "방문했던 곳을 다시 왔을 때, 이게 '새로운 사이클'인지 '기존 경로에 합류'하는 것인지 구분하는 것"이었습니다. 이를 위해 visited 배열 하나만 쓰는 것이 아니라, cycle 배열을 추가로 사용하여 상태를 관리하는 기법이 유효했습니다.

🛠️ 시행착오

처음에는 visit 배열 하나만 있으면 해결될 것이라 생각했습니다.

[오답 코드의 논리]

"메인 루프(for i, for j)에서 dfs가 호출되는 횟수가 곧 독립된 집합의 개수(Safe Zone 개수)가 아닐까?"

// 실패했던 코드 로직의 일부
if (!visit[i][j]) {
    safe += 1; // 호출할 때마다 무조건 카운트 증가
    dfs(i, j);
}

[문제점]

이 로직은 "새로운 경로가 기존에 이미 발견된 사이클로 합류하는 경우"를 고려하지 못합니다.

1. 이미 (0,0)에서 시작해 사이클을 하나 찾아서 safe=1이 되었습니다.
2. (1,0)은 아직 방문 안 했지만, 따라가다 보니 (0,0) 쪽의 사이클로 들어갑니다.
3. 위 로직대로라면 safe를 또 증가시켜 2가 됩니다.
4. 하지만 실제로는 기존 사이클로 합류하므로 Safe Zone을 추가로 설치할 필요가 없습니다.