[BOJ] 2463 - 비용

[백준] 1260 - DFS와 BFS

풀이

DFS란 깊이 우선 탐색으로, 간선을 통해 탐색한 정점으로 바로 이동해 그 정점에 연결된 간선을 다시 탐색하는 방식이다. BFS란 너비 우선 탐색으로, 현재 탐색하고 있는 정점의 모든 간선을 먼저 확인한 뒤에 그 다음 정점으로 가는 것이다..(뭔가 말이 어려운데?) 기초적인 문제인데도 틀린 상태로 방치되어 있어 몸풀기 겸 문제를 풀어보았는데, 코딩한지 너무 오래돼서 하루만에 못풀어서 결국 코드를 다 짜는데 일주일이나 걸렸다. 라이브러리를 쓸 지 귀차니즘 이슈로 고민을 조금 했지만 어쨌든 내가 일할때도 시험을 볼때도 라이브러리를 쓸 일이 없으니ㅠㅠ 라이브러리를 쓰지 않고 구현하는 것이 맞는 것 같다. 어쨌거나 아직 DFS와 BFS를 돌릴 수 있다는 사실을 알았으니 다음에는 이것보다는 좀 더 어렵지만 쉬운 문제로 풀어보는걸로 ~~

소스코드

#include <iostream>

int zipped_map[1005][1005] = { 0 };
int stack[1005] = { 0, };
bool visited_d[1005], visited_b[1005];
int s_size[1005] = { 0, };


void do_bfs(int v)
{
	int stack_last = 0, stack_index = 0, cur;
	stack[stack_last++] = v;

	while (stack_last != stack_index)
	{
		cur = stack[stack_index++];
		printf("%d ", cur);
		for (int i = 0; zipped_map[cur][i] != 0; ++i)
		{
			if (!visited_b[zipped_map[cur][i]])
			{
				visited_b[zipped_map[cur][i]] = 1;
				stack[stack_last++] = zipped_map[cur][i];
			}
		}

	}
}

void do_dfs(int v)
{
	printf("%d ", v);
	for (int i = 0; i<s_size[v]; ++i)
	{
		if (!visited_d[zipped_map[v][i]])
		{
			visited_d[zipped_map[v][i]] = 1;
			do_dfs(zipped_map[v][i]);
		}
	}
}

void sort(int* input, int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp;

	if (first < last)
	{

		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] <= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] > input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		sort(input, first, j - 1);
		sort(input, j + 1, last);
	}
}

int main(void)
{
	int n, m, v, a, b;
	//vector<int> map[1000];
	bool map[1005][1005] = { 0 };

	scanf("%d %d %d", &n, &m, &v);
	for (int i = 0; i < m; ++i) 
	{
		scanf("%d %d", &a, &b);
		//map[a].push_back(b);
		//map[b].push_back(a);
		zipped_map[a][s_size[a]++] = b;
		zipped_map[b][s_size[b]++] = a;
	}

	for (int i = 1; i <= n; ++i)
	{
		sort(zipped_map[i], 0, s_size[i] - 1);
	}

	visited_d[v] = 1;
	visited_b[v] = 1;
	do_dfs(v);
	printf("\n");
	do_bfs(v);

	return 0;
}