정올 1912 : 미로 탐색

문제: 정올 1912

 

풀이:

- DFS 문제이다

- 다만, 가장 낮은 숫자의 방 부터 방문해야 하므로, 미리 인접 리스트를 정렬해 놓는다

 (혹은 인접 리스트 대신에 힙을 써도 좋겠다. 즉, 힙을 원소로 가지는 벡터)

- 본인의 경우 2차원 벡터를 선언하고, 노드 갯수(n)를 받자 마자 Resize를 수행해 주었는데

  (왜냐하면 n을 받기 전에는 벡터를 n크기 만큼 초기화 할 수 없었으므로)

 해당 방법은 실행 시간 169ms로 90점 밖에 받지 못하였고, 처음 부터 그래프 노드를 100001 만큼 늘리고 시작하니

 실행시간 160ms로 통과되었다. 이상한 부분이다. 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;

//vector<vector<int>> v;
vector<int> v[100005];
int visited[100005];

void dfs(int st)
{
	if (visited[st]) return;

	printf("%d ", st);
	visited[st] = 1;
	for (int i = 0; i < v[st].size(); i++) {
		//if (visited[v[st][i]] == 0) {
			dfs(v[st][i]);
		//}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	//v.resize(n+1);
	int i1, i2;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &i1, &i2);
		v[i1].push_back(i2);
		v[i2].push_back(i1);
	}

	for (int i = 1; i <= n; i++)
		sort(v[i].begin(), v[i].end());

    dfs(1);
	return 0;
}