[백준 4803번] 트리 (C++)

문제링크 : https://www.acmicpc.net/problem/4803

4803번: 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, u, v;
vector<int>graph[501];
bool visited[501];

bool dfs(int cur, int post)
{
    visited[cur] = true;
    for(int i=0; i<graph[cur].size(); i++)
    {
        int next = graph[cur][i];
        if(next == post) continue; //부모 노드로 돌아가는 경우 스킵
        if(visited[next]) return false; 
        if(!dfs(next, cur)) return false;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    int idx = 0;
    while(1)
    {
        int result = 0;
        idx++; //케이스 번호
        cin >> N >> M;
        if(N==0 && M==0) break; 

        memset(visited, 0, sizeof(visited));
        memset(graph, 0, sizeof(graph));

        for(int i=0; i<M; i++)
        {
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        for(int i=1; i<=N; i++)
        {
            if(visited[i]) continue; //사이클을 이루면 패스
            if(dfs(i, 0)) result++;
        }

        if(result == 0) cout << "Case " << idx << ": No trees." << "\n";
        else if (result == 1) cout << "Case " << idx << ": There is one tree." << "\n";
        else cout << "Case " << idx << ": A forest of " << result << " trees." << "\n";
    }
    
}

사이클을 이루는 것을 확인하는 트리 문제이다.

현재 인덱스를 기준으로 dfs탐색을 돌려 이어진 것끼리 방문처리를 해준다.

다른 인덱스에서 탐색할때 이미 방문한 값을 또 방문하게 된다면 사이클을 이루는 것이기에 패스한다.

 

추가로 고려해야하는 경우는 부모 노드로 다시 돌아가는 경우이다.

이 경우 이미 방문했던 값은 맞지만, 관계없는 경우이기에 예외 처리를 해주어야 한다.

이를 위해 dfs 탐색에서 현재값과 동시에 부모노드 확인을 위해 직전값도 넘겨준다. (post)

 

이외에는 현재 값에 연결된 다음 값들이 이미 방문했는지 여부를 확인하고 참거짓을 리턴해주면 된다.

그리고 다음 값을 이어서 dfs로 탐색할때 주의해야 할 점이 있다.

if(!dfs(next, cur)) return false;

 

처음에 위 코드를  단순히 dfs(next, cur)로 하고 어차피 해당 탐색에서 방문했던 값을 만나게되면 알아서 fasle를 반환하니 상관없다고 생각했는데, 이러면 해당 dfs 탐색을 마치고 원래 처음 dfs로 넘어가 마지막 true를 반환하게 된다.

따라서 위 코드와 같이 연결된 다음값에 대한 dfs 탐색의 결과가 fasle일 때 바로 false를 반환하고 종료하도록 해줘야 한다.