BaekJoon 11725번: 트리의 부모 찾기

DFS를 이용해서 풀 수 있는 알고리즘이다.

 

DFS를 구현할 시 중요한 것은

1) 방문한 정점을 알아야 한다.

2) 더 이상 방문할 정점이 없으면 이전 정점으로 돌아간다.

3) 그래프가 분리되어 있을 수 있으므로 이를 꼭 확인해야 한다.

 

DFS의 장점은

1) 현재 경로 상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.

2) 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다.

3) BFS보다 구현이 간단하다.

 

DFS의 단점은

1) 단순 검색 속도는 BFS보다 느리다.

2) 해가 업는 경우 빠질 가능성이 있다.

   (임의의 깊이를 지정한 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색한다)

3) 깊이 우선 탐색은 해를 구하면 종료된다. 고로 구한 해가 최단 경로가 된다는 보장이 없다.

 

풀이법

1) 트리에서 루트 값을 1로 줬기 때문에 1을 기준으로 dfs를 활용한다.

2) 트리 상에 연결된 vertex 값이 주어졌기 때문에 이를 연결한 배열을 사용한다.(양방향 연결)

3) parent 배열과 visited 배열을 이용하여 재귀함수를 통해 문제를 해결한다.

#include <iostream>
#include <vector>
#define INF 100001
using namespace std;

int n;
vector<int>arr[INF];
int parent[INF];
bool visited[INF];
void dfs(int node)
{
	visited[node] = true;
	for (int i = 0; i < arr[node].size(); i++)
	{
		int next = arr[node][i];
		if (!visited[next])
		{
			parent[next] = node;
			dfs(next);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	dfs(1);
	for (int i = 2; i <= n; i++)
	{
		cout << parent[i] << "\n";
	}
}

한계점 및 개선사항

최근 dfs를 거의 이용하지 않고 bfs로만 문제를 풀다보니 해법을 생각해내는 것이 어려웠다.

다른 블로그의 도움을 받아 해결하였으나 추후 보지 않고 재 코딩하여 문제를 성공시켰다.

관련 개념에 대해서 깊이 있게 공부 후 완전히 내 것으로 만들 수 있도록 더 노력해야겠다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest

solved.ac/profile/pearlcrum