백준알고리즘 11725번, 트리의 부모 찾기

연결된 두 vertex의 정보가 주어질 때 각 노드의 부모를 찾아서 2번부터 출력해주는 문제입니다. 처음에 접근할때는 행렬로 풀려고 했는데, 다익스트라 알고리즘 공부하면서 인정리스트의 장점을 실감하게 되어서 vector를 사용해 인정리스트를 만들었고, 큐를 사용해 BFS로 풀었습니다. 재귀함수를 이용해 DFS로 풀 수도있겠지만 뭔가 함수를 계속 호출하는건 성능에 안좋을꺼같아 BFS로 풀었습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;

int main(void) {
 vector<int> adj[100001];  ?//인접행렬
 bool visited[100001] = { false }; //방문확인
 queue<int> q;
 int t;
 int n1, n2;
 int curr, next,parent;
 for (int i = 1; i < 100001; i++) {
  adj[i].push_back(0); //각 노드 벡터의 0번째는 부모노드를 가르킴, 기본값 0 설정
 }

#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif

 scanf("%d\n", &t);
 for (int i = 1; i < t; i++) {
  scanf("%d %d\n", &n1, &n2);
  adj[n1].push_back(n2); //각 노드에 연결 정보저장
  adj[n2].push_back(n1); //각 노드에 연결 정보저장
 }

 q.push(1); //1번 노드부터 시작
 while (!q.empty()) {?//BFS
  curr = q.front();
  q.pop();

  visited[curr] = true;
  for (int i = 1; i < adj[curr].size(); i++) {

    next = adj[curr][i];

    if (visited[next] == true)
     continue;

    else {
     adj[next][0] = curr;
     q.push(next);

    }
   }
  }

 for (int i = 2; i <= t; i++) {
  printf("%d\n", adj[i][0]);
 }
 

 

#ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
#endif

 return 0;

}

Contents