[백준] 16724번 피리 부는 사나이 (C++)

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

 

 

이 문제는 격자 그래프가 주어졌을때 각 칸마다 어떤 행동을 취할지 알파벳으로 주어지고 행동을 취했을때 이미 방문했던(사이클)이 발생한 경우

그 사이클은 안전지대를 하나를 놔야하며 이때 최소한의 안전지대의 개수를 출력하는 문제이다.

 

사이클을 판별하기 위해선 bool 방문배열을 사용하여 이전에 방문했던 경우 사이클로 판단하여 개수를 하나씩 늘리면 가능하다

하지만 이런 경우가 있을 수 있다

 

만약 사이클이 존재하는 경로가 있고 이전에 방문하지 않았던 경로가 사이클에 진입하는 경우가 있을 수 있다.

이 경우에는 같은 사이클이지만 서로 다른 사이클로 판단한다.

 

따라서 int형 방문배열을 사용하여 처음엔 -1로 초기화 시켰으며

 

이전에 cnt값을 1로 생성하여 dfs호출이 끝났을때 값을 하나씩 증가시켜주었다.

 

위와 같은 경우는 dfs함수 내에서 조건문을 적절히 잘 사용하면 같은 사이클인지 판별할 수 있다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M;
char graph[1001][1001];
int dp[1001][1001];
int cnt;

int dfs(int x, int y) {
    if(dp[x][y] != -1) return dp[x][y];
    dp[x][y] = cnt;

    if(graph[x][y] == 'U') {
        dp[x][y] = dfs(x-1, y);
    }
    else if(graph[x][y] == 'D') {
        dp[x][y] = dfs(x+1, y);
    }
    else if(graph[x][y] == 'L') {
       dp[x][y] = dfs(x, y-1);
    }
    else dp[x][y] = dfs(x, y+1);

    return dp[x][y];
}

void solve() {

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(dp[i][j] == -1) {
                dfs(i, j);
                cnt++;
            }
        }
    }

    set<int> st;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            st.insert(dp[i][j]);
        }
    }

    cout << st.size();

    // for(int i = 0; i < N; i++) {
    //     for(int j = 0; j < M; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    // cout << cnt;
}

void Init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            dp[i][j] = -1;
        }
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }

    Init();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();

    return 0;
}

 

 

회고록

내가 짠 코드는 별로 좋지 않은 코드인것 같다

이중 for문에서 방문하지 않았던 칸에 대해서 dfs를 호출하고 끝난 경우 바로 답이 나올거 같은데

 

현재 내 코드에서는 한번더 격자를 탐색하여 set에 넣어주는 과정이 존재한다.

재귀쪽에서 많이 햇갈려서 시간이 많이 허비가되었다