Graph B11725

개요

백준 문제 11725번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 35분
https://www.acmicpc.net/problem/11725

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

계획한 풀이법

문제를 보고 루트 없는 트리가 주어진다길래 무슨 말인가 했는데
루트를 1이라고 생각하고 입력이 주어진다는 말이었다.
풀이는 어쨌거나 트리는 최상위 루트가 존재해야하는데 그것이 1로 주어진다고 하여서 이를 힌트로 삼았다.
기준을 1로(시작점) 잡으면 그 이후 부터는 BFS로 이동하기 전 노드가 이동하려는 노드의 부모 노드가 되니 이를 마킹하면 되는 문제이다.

코드

//PM 6:17
// 구상~ 
//PM 6:34
// 구현~
//PM 6:55
//완

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100001;

vector<int> graph[MAX];
int visit[MAX];
int N;

void init()
{
	cin >> N;
	for(int i=0;i<N+1;i++)
	{
		visit[i] = 0;
	}
}

void edgeBiConnect(int v,int e)
{
	graph[v].push_back(e);
	graph[e].push_back(v);


}
//루트가 있을때 root -> e
void edgeOneConnect(int v)
{
	graph[1].push_back(v);
}

void BFS(int startV)
{
	queue<int> q;
	int curV;


	for(int i=0;i<graph[1].size();i++)
	{
		q.push(graph[1][i]);
		visit[graph[1][i]] = 1;
	}

	while(q.size() != 0)
	{
		curV = q.front();
		q.pop();

		for(int i=0;i<graph[curV].size();i++)
		{

			if(visit[graph[curV][i]] == 0)
			{
				q.push(graph[curV][i]);
				visit[graph[curV][i]] = curV;
			}
			
		}
	}


}

void solve()
{
	int v,e;
	for(int i=0;i<N;i++)
	{
		cin >> v >> e;
		if(v == 1)
		{
			edgeOneConnect(e);
		}
		else if(e == 1)
		{
			edgeOneConnect(v);
		}
		else
		{
			edgeBiConnect(v,e);
		}
	}
	BFS(1);
	for(int i=2;i<=N;i++)
	{
		cout << visit[i] << "\n";
	}
}


int main()
{
	init();
	solve();

}

느낀 점

• 문제 자체는 쉬웠으나 한번에 고민한 것이 맞았고 코드도 나름 간결하게 짠 것 같아 만족한 풀이