[C언어] 백준 1260 : DFS와 BFS

https://www.youtube.com/watch?v=rand1XTwEnE&ab_channel=%EC%BD%94%EB%8D%B0%ED%92%80
이사람 미쳤음 이해가 너무 잘됐다.
일단 BFS는 아직 보지도 않았다. 아마 피신 끝나고 진행하지 않을까 싶다.
먼저 백트래킹파트를 다 공부하고 피신 하려고 했는데 백트래킹에서 DFS를 써야되는 부분이 있어서 넘어오게 되었다.
근데 또 DFS를 하려면 스택을 알아야하는데, 이부분은 오늘 문제를 풀어봐서 다행이였다. 우연이였다.
BFS를 하려면 큐의 개념을 알고 있어야하는데, 큐는 C언어에서 매우 불리하다고 들었다. 그래서 나아중에 C++을 하든 node.js를 할 때 같이 하지않을까 싶다.

코드

#include <iostream>
#include <stdio.h>
#include <queue>
#include <memory.h>
#include <algorithm>
using namespace std;

int arr[1001][1001];
int visit[1001];
int N, M, V;
int u, v;

void dfs(int x) // 재귀 dfs
{
	int i = 0;

	visit[x] = 1; // 방문 표시
	printf("%d ", x); // 방문한 점 출력

	for (i = 1; i <= N; i++)
		if (arr[x][i] == 1 && visit[i] == 0)
		{
			
			dfs(i);
		}
	if (i == N) return; // i가 N개의 모든 점을 검사했다면 반환
}
/*
void bfs(int x)
{
	queue<int> q; // 큐 생성
	int i = 0;

	q.push(x); // 시작점 큐에 삽입

	while (!q.empty()) // 큐에 원소가 하나도 없을 시 탈출
	{
		int next_x = q.front(); // 큐 맨앞의 원소를 다음 탐색할 점으로 지정
		visit[next_x] = 1; // 방문 표시
		printf("%d ", next_x); // 방문 한 점 출력
		q.pop(); // 큐 맨 앞 데이터 삭제

		for (i = 1; i <= N; i++)
			if (arr[next_x][i] == 1 && visit[i] == 0)
			{
				//next_x점과 i점이 연결되어있고 i점은 방문기록이 없다면
				q.push(i); // 큐에 i점 삽입
				visit[i] = 1; // i점은 미리 방문표시(미리 하지 않으면 중복으로 방문할 수도 있음)
			}
	}
}
*/
int main()
{
	scanf("%d %d %d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &u, &v);
		// arr = 각 점의 연결 정보를 알려주는 행렬
		arr[u][v] = 1;
		arr[v][u] = 1;
	}

	dfs(V);
/*
	printf("\n");
	memset(visit, 0, sizeof(visit)); // 방문기록 초기화

	bfs(V);

*/

}

https://cocoon1787.tistory.com/148
이사람것도 봤었는데,
처음에 왜 이차원배열에 1을 넣어주는지, 어떻게 되돌아가는지 잘 이해가 안되었지만, 영상을 보고 나니 이해가 되었다.
제출은 다른걸로 했지만, 이분이 되게 상세하게 정리해주셨다.
배열을 돌아가면서, 이차원배열에 1로 초기화한곳만 쏙쏙 들어가며 재귀를 돌린다. 또한 방문한곳은 1로 바꾸어주며, 방문하지않은곳만 들어간다.

시간이 얼마 안남아서, DFS위주로 하다가 나중에 다시 공부하러 되돌아 올 것이다.