https://www.acmicpc.net/problem/11725
문제
> 루트 없는 트리가 주어진다.
이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.접근
DFS로 깊이우선 탐색을 사용해서 입력받은 트리를 탐색한다.
DFS의 구조에서 현재 스택에 대해 자식 노드를 추가해주는 부분이 있다.
여기서 자식을 넣으면서 동시에 부모 자식 관계를 담을 rst벡터에 자식을 인덱스로 해서 현재의 부모를 값으로 저장한다.
이때 연결 관계상의 모든 노드를 탐색하는 것이므로 자식이 아닌 노드도 들어올 수있다(상위 노드). 따라서 깊이 우선으로 탐색하며 이미 탐색한 노드는 방문처리를 해줘서 자식 탐색 때, 중복으로 들어와 오류가 발생하지 않도록 해준다.
문제해결
> 노드의 개수를 입력받고, 각 노드별 연결 상태인 tree 벡터를 이중 벡터로, 방문처리용 visited 부울형 벡터, 결과를 저장할 rst 벡터를 N+1크기로 선언해준다.
> 입력으로 들어오는 연결관계는 N-1개이므로 N-1만큼 반복하며 관계를 입력받는다.
양방향으로 받아주고 DFS상에서 트리가 오름차순으로 만들어지기 위해 정렬해준다.(안해도됨)
> DFS에 루트인 1을 넣고 호출한 뒤 결과 rst를 출력한다.
> 스택으로 DFS를 구현한다. 자식을 탐색하는 for(auto a:tree[t]에서 자식이 아닌 관계를 넣는걸 방지하기 위해 미리 t에대해 방문처리를 해준다.
> 예로 2의 자식인 4가 들어갔을 때 이 방문처리를 통해 4의 부모인 2가 연결 관계때문에 탐색대상에 들어가 2의 부모가 4가 되어버리는 상황이 막아진다.
> 자식을 골라냈으면 자식을 인덱스로 rst 벡터에 자식의 부모인 t를 값으로 저장한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
int N;
vector<vector<int>> tree;
vector<int> rst;
vector<bool> visited;
void DFS(int start)
{
stack<int> s;
s.push(start);
while (!s.empty())
{
int t = s.top();
s.pop();
visited[t] = true;
for (auto a : tree[t])
{
if (!visited[a])
{
s.push(a);
rst[a] = t;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
tree.resize(N+1, vector<int>());
visited.assign(N + 1, false);
rst.assign(N + 1, 0);
int n = N - 1;
while (n--)
{
int a, b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for (int i = 1; i <= N; i++) sort(tree[i].begin(), tree[i].end(), greater<int>());
DFS(1);
for (int i = 2; i <= N; i++)
cout << rst[i] << '\n';
}
후기
처음에 깊이우선 탐색으로 해야 부모 자식간을 확인할 수 있고 너비로 하면 관계가 희석될거 같았는데 막상 다 짜고 쭉 따라가보니 어차피 각각의 자식에 대해 탐색하고 서로를 부모자식으로 저장하는거니 DFS, BFS 다 상관 없을것 같다.
그리고 main문의 정렬도 DFS의 순서에 대해서 오름차순으로 탐색하기 위해 내림차순으로 미리 정렬했는데
이 또한 굳이 필요가 없다. 위 와 같은 맥락으로 순서가 어쨋던 방문처리가 있고 각각의 경우에서 따지는것이기 때문이다.
두 과정을 그동안 했던 짬으로 감으로 넣고 짰지만
다 하고 다시 보니 다르게 보였다.
그래프 탐색의 구조에 대해 이해도가 조금 상승하는 기회였다.
