4803 트리 python, c++

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

4803번: 트리

 

 

 

 

 

 

 

문제 접근

첫 번째는 union & find로 풀었다.

union을 하는 과정에서 만약 이미 union을 해서 같은 트리에 있는데, 한번 더 시도하는 것이라면 트리가 아니게 된다.

왜냐하면 트리안에서 간선이 하나 더 생겨버리면 어떻게 연결되더라도 사이클 형태로 만들어지기 때문이다.

이걸 생각하는 과정에서 find에서 경로압축을 해도 무관하다는 정보까지 생각할 수 있었다.

 

union&find에서 사용할 parent에서 사이클이 아니라면 False처리를 해주기 위해 2차원 배열로 만들기로 했다.

그리고 문제에서 지시한 모든 간선을 계산한 후에는 False가 아닌 루트 노드의 개수 = 트리의 개수라고 보면 된다.

 

Union & Find 알고리즘

Union & Find 알고리즘

 

 

 

 

 

두 번째는  DFS로 풀었다.

사실 dfs나 bfs나 방식은 비슷하다고 생각한다.

그냥 stack을 쓰냐 queue를 쓰냐 차이인데 푸는 방식을 이해하면 둘 중 어떤 걸로 풀어도 상관없다고 생각했다.

탐색인 만큼 필요한 변수를 우선 생성해야 한다.

1. 들렀는지 안들렀는지 판단하는 배열 visitied

2. 간선을 저장해둘 2차원 배열 edge

그리고 DFS를 하는 과정에서 circle이 생겼는지 판단해야 한다.

판단하는 방법은 visited에서 True처리된(방문한) node를 한번 더 접근하려고 하면 circle이 생긴 것이다.

필자는 함수로 만들어서 return값으로 판단하도록 만들었다.

 

 

 

 

 

 

 

 

 

+) DFS를 푸는 과정에서...

처음에 시간을 더 줄여보겠다고 간선을 한쪽만 추가를 했었다.

if x < y:
      edge[x].append(y)
    else:
      edge[y].append(x)

이렇게 무조건 작은 값에 등록하도록 했고 DFS에서도 이 방법을 고려해서 탐색하도록 만들었다.

하지만 이경우에

5 4

1 3

1 4

1 5

2 3

이렇게 입력이 주어진다면 문제가 발생했다.

백준에 천사가 올려준 테스트케이스

위 테스트케이스 13까지 진행했을 때, 11과 12에서 틀리게 나와서 2시간 동안 생각하다가 왜 틀렸는지 찾아냈다ㅜㅜ

물론 위 테스트케이스를 그려보진 않았다. 노드를 1부터 100까지 그려서 간선을 이을 자신은 없었다. 하핳

 

 

 

 

 

 

 

 

 

메모리와 시간 (python)

 

위는 union & find이고 아래는 DFS

31256

272

47828

392

 

DFS가 훨씬 느렸고 메모리도 많이 잡아먹었다.

 

 

 

 

 

 

C++ vector 사용법

C++ vector 사용법

 

 

 

 

 

 

 

 

 

코드  union&find

python

import sys

input = sys.stdin.readline
"""
union-find
만약 union을 하는데 이미 있으면 트리에서 제외
 -> 2차원 배열로 트리가 아니면 False처리.
모든 간선 계산 후 -> 루트노드의 개수 = 트리의 개수

트리가 아니다 = 사이클이 생겼다.
사이클이 생긴다 = 트리 내부에서 노드간에 간선이 하나 더 연결됐다.
-> find에서 경로압축을 하더라도 상관없다.
   이미 union에서 해당 루트노드를 가르키는데 한번 더 가르키라고 지정해버리는 경우가 사이클이 생기는 경우기 때문
"""


def find(x):
  if parent[x][0] != x:  #루트노드가 아니면
    parent[x][0] = find(parent[x][0])  #경로압축, 루트노드 찾으러 가기
    return parent[x][0]
  return x  #루트노드를 찾으면 반환


def union(x, y):
  a = find(x)
  b = find(y)
  if a < b:
    parent[b][0] = a
    if parent[a][1]:
      parent[a][1] = parent[b][1]
  elif a > b:
    parent[a][0] = b
    if parent[b][1]:
      parent[b][1] = parent[a][1]
  elif a == b:
    parent[a][1] = False  #사이클이 생겼으니 False


case = 1
while True:
  n, m = map(int, input().split())
  cnt = 0
  if n == 0:
    break
  parent = [[j for i in range(2)] for j in range(n + 1)]

  #union 처리
  for i in range(m):
    fir, sec = map(int, input().split())
    union(fir, sec)

  #루트노드 찾기
  for i in range(1, n + 1):
    if parent[i][0] == i and parent[i][1]:  #루트노드면서 False가 아닌 것
      cnt += 1

  #출력
  if cnt == 0:
    print("Case ", case, ": No trees.", sep="")
  elif cnt == 1:
    print("Case ", case, ": There is one tree.", sep="")
  else:
    print("Case ", case, ": ", "A forest of ", cnt, " trees.", sep="")
  case += 1

 

 

 

C++

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> parent;
// parent[?][1]에 사이클이 생기면 1로 저장

int find(int x) {
  if (parent[x][0] == x) {
    return x;
  }
  return parent[x][0] = find(parent[x][0]);
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y) {
    parent[y][0] = x;
    if (parent[y][1] == 1) {
      parent[x][1] = 1;
    }
  } else if (x > y) {
    parent[x][0] = y;
    if (parent[x][1] == 1) {
      parent[y][1] = 1;
    }
  } else { // x==y
    parent[x][1] = 1;
  }
}

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

  int c = 1;
  while (true) {
    int n, m, cnt = 0;
    cin >> n >> m;
    if (n == 0)
      break;
    parent.assign(n + 1, vector<int>(2, 0));
    for (int i = 1; i < n + 1; i++) {
      parent[i][0] = i;
    }

    // merge
    for (int i = 0; i < m; i++) {
      int start, end;
      cin >> start >> end;
      merge(start, end);
    }

    //루트노드로 사이클 확인
    for (int i = 1; i < n + 1; i++) {
      if (parent[i][0] == i && parent[i][1] == 0) {
        cnt++;
      }
    }

    //출력
    cout << "Case " << c << ": ";
    if (cnt == 0) {
      cout << "No trees.\n";
    } else if (cnt == 1) {
      cout << "There is one tree.\n";
    } else {
      cout << "A forest of " << cnt << " trees.\n";
    }
    c++;
  }
}

 

 

 

 

 

 

 

 

 

 

코드  DFS

python

import sys

input = sys.stdin.readline
"""
DFS

# 간선을 저장하는 2차원배열 생성
추가로 배열하나에 들렀는지 체크하는 배열 생성(visited)
탐색을 통해서 visited에 이미 들려서 true라면 트리가 아닌걸로
visited에 true라면 트리인지 체크할필요 없음.
"""

#DFS로 circle이 생겼는지 판단후 리턴
def DFS(start):
  circle = False
  stack = list()
  stack.append((start, 0))
  while stack:
    node, parent = stack.pop()
    if not visited[node]:
      visited[node] = True
      for i in edge[node]:
        if i!=0 and i!=parent:
          stack.append((i, node))
    else:
      circle = True

  return circle


case = 1
while True:
  n, m = map(int, input().split())
  if n == 0: break

  edge = [[0 for i in range(n + 1)] for j in range(n + 1)]
  visited = [False for i in range(n + 1)]
  cnt = 0

  #입력
  for i in range(m):
    x, y = map(int, input().split())
    # if x < y:
    edge[x].append(y)
    # e lse:
    edge[y].append(x)  #간선 추가

  for i in range(1, n + 1):
    if visited[i]:
      continue
    if not DFS(i):
      cnt += 1

  #출력
  if cnt == 0:
    print("Case ", case, ": No trees.", sep="")
  elif cnt == 1:
    print("Case ", case, ": There is one tree.", sep="")
  else:
    print("Case ", case, ": ", "A forest of ", cnt, " trees.", sep="")
  case += 1

 

 

 

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> edge;
vector<int> visited;

bool DFS(int start) {
  vector<pair<int, int>> stack;
  stack.push_back(make_pair(start, 0));

  while (!stack.empty()) {
    int node, parent;
    node = stack.back().first;
    parent = stack.back().second;
    stack.pop_back();

    if (!visited[node]) {
      visited[node] = true;
      for (int i = 0; i < edge[node].size(); i++) {
        if (edge[node][i] != parent) {
          stack.push_back(make_pair(edge[node][i], node));
        }
      }
    } else
      return true;
  }
  return false;
}

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

  int testCase = 1;
  while (true) {

    //변수 생성
    int n, m, cnt = 0;
    cin >> n >> m;
    if (n == 0)
      break;

    edge.assign(n + 1, vector<int>(0));
    visited.assign(n + 1, false);

    //간선 등록
    for (int i = 0; i < m; i++) {
      int x, y;
      cin >> x >> y;
      edge[x].push_back(y);
      edge[y].push_back(x);
    }

    // DFS로 트리 개수 파악
    for (int i = 1; i < n + 1; i++) {
      if (visited[i]) {
        continue;
      }
      if (!DFS(i)) {
        cnt++;
      }
    }
    switch (cnt) {
    case 0:
      cout << "Case " << testCase << ": No trees.\n";
      break;
    case 1:
      cout << "Case " << testCase << ": There is one tree.\n";
      break;
    default:
      cout << "Case " << testCase << ": A forest of " << cnt << " trees.\n";
    }
    testCase++;
  }
}

아직 C++이 익숙하지가 않아서 검색을 많이 해봤다.

DFS에서 억지로 vector와 pair를 써보려다가 더 복잡해진 것 같기도...