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

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

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로(간선)가 있다면, 두 정점은 연결돼 있다고 한다. 연결 요소는 모든 정점이 서로 연결돼 있는 정점의 부분집합이다. 그래프는 하나 이상의 연결 요소로 이루어져 있다.

 

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해 경로가 유일하다.

 

그래프가 주어질 때, 트리의 개수를 세는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• n ≤ 500
• m ≤ n(n-1)/2
• 출력
  • "No trees.": 그래프에 트리가 없는 경우
  • "There is one tree.": 그래프에 트리가 1개 있는 경우
  • "A forest of T trees.": 그래프에 트리가 T개 있는 경우

 

그래프에 있는 트리의 개수를 세기 위해선 그래프에 있는 모든 정점에서 dfs 함수를 돌려 사이클이 있는지 확인해야 한다. dfs 함수를 진행하면서 사이클이 있다면 트리가 아닌 거고, 사이클이 없다면 트리라고 할 수 있다. 모든 정점에서 dfs 함수를 돌려야 하는 이유는 어떤 정점을 루트로 두냐에 따라 다른 트리라고 볼 수 있기 때문이다.

 

간선을 양방향으로 저장하되, 트리는 사이클이 없어야 하므로 단방향으로 진행해야 한다. 따라서 visit 배열을 통해 방문한 적이 있다면 사이클로 간주하고 트리 개수에 더하지 않아야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M이 0, 0으로 들어올 때까지 테스트 케이스 입력받기
   1. 테스트 케이스마다 vector의 크기가 동적으로 바뀌어야 하기 때문에 assign() 함수를 사용해 n+1만큼의 크기를 할당하기
   2. 간선 정보를 양방향으로 입력받기
   3. 1번부터 N번까지 방문하지 않은 간선들에 대해 dfs 함수 돌리기 (파라미터: 현재 노드, 이전 노드)
      1. dfs를 돌리는 노드 번호를 방문 체크
      2. 노드와 연결된 모든 정점에 대해, 연결된 해당 노드가
         1. 이전 노드와 동일하거나 방문한 적이 있거나 (해당 노드, 현재 노드)로 dfs를 돌렸을 때 false가 나온다면 사이클이므로 false 반환
         2. 위 조건을 모두 만족하지 않으면 true 반환 & 트리 개수 1 증가
   4. 트리 개수에 맞춰 다르게 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int,int>
using namespace std;

int n,m,u,v,idx;
vector<vector<int>> edge;
vector<int> visit;

bool dfs(int idx, int before) {
    visit[idx] = true;

    for (auto next : edge[idx]) {
        if (next==before) continue;
        if (visit[next]) return false;
        if (!dfs(next,idx)) return false;
    }
    return true;
}

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

    while (1) {
        cin >> n >> m;
        if (n==0 && m==0) break;
        
        int tree = 0;
        idx++;

        edge.assign(n+1, vector<int>(0,0));
        visit.assign(n+1, false);
        for (int i=0; i<m; i++) {
            cin >> u >> v;
            edge[u].emplace_back(v);
            edge[v].emplace_back(u);
        }

        for (int i=1; i<=n; i++) {
            if (!visit[i] && dfs(i,0)) tree++;
        }

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