문제
https://www.acmicpc.net/problem/1260
풀이
더보기
/*
DFS, BFS 개념 파악 문제
양방향 확인 필요
DFS : 깊이 우선 탐색
- 방문한 곳을 끝까지 탐색
BFS : 너비 우선 탐색
- 한 Depth를 다 훑고 가는 탐색
*/
using System;
namespace Algorithm
{
class Program
{
static int N, M, V;
static bool[,] nodes; // 인접 행렬
static bool[] visited; // 방문 여부
// 방문 기록 초기화
static void Reset()
{
for(int i = 0; i < visited.Length; i++)
{
visited[i] = false;
}
}
// BFS에서 다음 Depth 탐색을 위한 대기열
static Queue<int> bfsQueue = new Queue<int>();
static void Main(string[] args)
{
Answer();
}
static void Answer ()
{
// 문제에서 주어지는 입력값
int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
N = inputs[0];
M = inputs[1];
V = inputs[2];
nodes = new bool[N+1, N+1];
visited = new bool[N+1];
for(int i = 0; i < M; i++)
{
int[] points = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
nodes[points[0], points[1]] = true;
nodes[points[1], points[0]] = true; // 양방향 처리
}
// 결과 출력
DFS(V);
Reset();
Console.WriteLine();
BFS(V);
}
static void DFS(int v)
{
visited[v] = true;
Console.Write($"{v} ");
for(int i = 1; i <= N; i++)
{
if(nodes[v, i] == true && !visited[i]) // 인접 행렬인데 방문을 안했다면 방문하러 고고
{
DFS(i);
}
}
}
static void BFS(int v)
{
visited[v] = true;
Console.Write($"{v} ");
for(int i = 1; i <= N; i++)
{
if(nodes[v, i] == true && !visited[i])
{
if(!bfsQueue.Contains(i)) // 이미 대기 중이라면 패스
bfsQueue.Enqueue(i);
}
}
if(bfsQueue.Count > 0) // 대기가 없을 때까지 재귀
BFS(bfsQueue.Dequeue());
}
}
}
Comment
- 양방향 처리 반드시 해줘야만 방문 행렬을 명확히 처리할 수 있다.
- 어렵게 생각할 것 없다.
> DFS는 깊게 파고드는 것
> BFS는 행, 열로 따지자면 한 행을 다 파악하고 가는 것 그리고 대기열(Queue)에 담아두었다가 하나씩 꺼내서 출력
- 헷갈려서 그림으로 그려가면서 확실히 이해했다.
https://github.com/SolHaan/algorithm_study
'프로그래밍 문제' 카테고리의 다른 글
[백준][C#] 1072번, 게임 (0) | 2024.09.12 |
---|---|
[백준][C#] 15552번, 빠른 A+B (0) | 2023.10.12 |
[백준][C#] 2480번, 주사위 세개 (0) | 2023.10.12 |
[백준][C#] 2525번, 오븐 시계 (1) | 2023.10.12 |
[백준][C#] 2884번, 알람 시계 (0) | 2023.10.12 |