[C] 백준 - 1260번: DFS와 BFS

5월 17일(수) - 그래프와 순회 (1260번)

1260번: DFS와 BFS

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 가장 기본적인 dfs와 bfs 구조를 활용

- 다만 두 가지의 탐색을 동시에 사용해야하기에, dfs_visited 배열과 bfs_visited 배열로 나누어서 활용

- dfs 구조는 "2606번: 바이러스"에서의 풀이를 활용

- bfs 구조는 큐를 사용해서 새롭게 만들어야함

- dfs와 bfs 모두 매번 변수 start를 출력하면서 최종적인 출력 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int arr[1001][1001];
int dfs_visited[1001];
int bfs_visited[1001];
int queue[1001];

void dfs(int start, int N)
{
	if (dfs_visited[start] == 1)
	{
		return;
	}

	dfs_visited[start] = 1;
	printf("%d ", start);
	for (int i = 1; i <= N; i++)
	{
		if (arr[start][i] == 1 && dfs_visited[i] == 0)
		{
			dfs(i, N);
		}
	}

	return;
}

void bfs(int start, int N)
{
	int front = 0;
	int rear = 0;
	int pop;

	printf("%d ", start);
	queue[0] = start;
	rear++;

	bfs_visited[start] = 1;
	while (front < rear)
	{
		pop = queue[front];
		front++;

		for (int i = 1; i <= N; i++)
		{
			if (arr[pop][i] == 1 && bfs_visited[i] == 0)
			{
				printf("%d ", i);
				queue[rear] = i;
				rear++;
				bfs_visited[i] = 1;
			}
		}
	}

	return;
}

int main(void)
{
	int N, M, V;
	scanf("%d %d %d", &N, &M, &V);

	int from, to;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &from, &to);
		arr[from][to] = 1;
		arr[to][from] = 1;
	}

	dfs(V, N);
	printf("\n");
	bfs(V, N);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ