[C++] 백준/Gold/16724. 피리 부는 사나이

문제: 음악 프로그램 (백준 16724번)

문제 분석

이번 문제는 주어진 그래프에서 사이클의 개수를 구하는 문제이다.

입력 형식을 보면 지도 밖으로 나가는 방향의 입력은 주어지지 않기 때문에 결국 화살표들은 사이클을 최소 1개 이상 무조건 생성을 하게 되어있다.

DFS를 사용한 사이클 개수 찾기

사이클 개수를 구하기 위해 DFS를 활용한다.
이때, 사이클 판별을 위해 visited와 finish 배열을 사용한다.

1. visited[y][x]는 현재 칸이 방문되었는지 여부를 저장한다.
2. finish[y][x]는 현재 칸에 대한 탐색이 끝났는지를 나타낸다.

DFS를 통해 현재 칸에서 다음 칸으로 이동하면서, 다음과 같은 조건으로 사이클을 판별한다.

• 다음 칸이 방문된 적이 있지만 탐색이 끝나지 않은 칸이라면, 이는 사이클이 형성되었음을 의미한다.
• 모든 탐색이 끝난 칸은 finish 배열에 표시하여 다시 방문하지 않도록 한다.

코드

#include <bits/stdc++.h>
using namespace std;

void dfs(int x, int y, vector<vector<pair<int, int>>>& graph, vector<vector<bool>>& finish, vector<vector<bool>>& visited, int& cycle) {
    visited[y][x] = true;

    int xx, yy; tie(yy, xx) = graph[y][x]; // 현재 칸에서 이동할 다음 칸
    if (!visited[yy][xx]) { 
        dfs(xx, yy, graph, finish, visited, cycle); // 다음 칸으로 이동
    }
    else if (!finish[yy][xx]) { 
        cycle++; // 사이클 발견
    }
    finish[y][x] = true; // 현재 칸 탐색 완료
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> graph(n, vector<pair<int,int>>(m));

    // 그래프 초기화
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            char ch = s[j];
            if (ch == 'U') graph[i][j] = { i - 1, j };
            if (ch == 'D') graph[i][j] = { i + 1, j };
            if (ch == 'L') graph[i][j] = { i, j - 1 };
            if (ch == 'R') graph[i][j] = { i, j + 1 };
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m)), finish(n, vector<bool>(m));
    int answer = 0;

    // 모든 칸에 대해 DFS 실행
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j]) {
                dfs(j, i, graph, finish, visited, answer);
            }
        }
    }
    cout << answer;
}