SMALL
https://www.acmicpc.net/problem/24444
24444번: 알고리즘 수업 - 너비 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방
www.acmicpc.net
- 문제
- 문제풀이
먼저, 입력 값을 받아와서 그래프를 초기화한다. 각 정점마다 인접한 정점을 리스트에 추가한다.
그리고, 방문 여부 배열과 정점 방문 순서 배열을 초기화한다. 방문 여부 배열은 모두 false로, 정점 방문 순서 배열은 모두 0자동 설정된다.
다만 내림차순으로 정렬하기 때문에 그래프를 내림차순으로 정렬해준다.
BFS 함수를 호출합니다. BFS 함수는 Queue를 사용하며, 현재 정점을 방문하고 방문 순서를 기록한 뒤 인접한 정점들에 대해서 BFS를 순차적으로 사용한다.
마지막으로, 정점 방문 순서 배열을 출력한다. 만약 해당 정점이 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
- 코드 1
namespace YONGYONG2
{
using System;
using System.Collections.Generic;
using System.Text;
public class Program
{
static bool[] BFSbool;
static int[] BFSlist;
static int count = 1;
static List<int>[] graph;
public static void BFS(int V)
{
Queue<int> queue = new Queue<int>();
queue.Enqueue(V);
BFSbool[V] = true;
BFSlist[V] = count;
count++;
while (queue.Count != 0)
{
int temp = queue.Dequeue();
foreach(int next in graph[temp])
{
if (!BFSbool[next])
{
BFSbool[next] = true;
queue.Enqueue(next);
BFSlist[next] = count;
count++;
}
}
}
}
public static void Main(string[] args)
{
using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
string[] input = sr.ReadLine().Split(' ');
int N = int.Parse(input[0]);
int M = int.Parse(input[1]);
int V = int.Parse(input[2]);
graph = new List<int>[N + 1];
for (int i = 1; i <= N; i++)
{
graph[i] = new List<int>();
}
BFSbool = new bool[N + 1];
for (int i = 0; i < M; i++)
{
string[] line = sr.ReadLine().Split();
int a = int.Parse(line[0]);
int b = int.Parse(line[1]);
graph[b].Add(a);
graph[a].Add(b);
}
for (int i = 1; i <= N; i++)
{
graph[i].Sort();
graph[i].Reverse();
}
BFSlist=new int[N+1];
BFS(V);
for (int i = 1; i <= N; i++)
{
sw.WriteLine(BFSlist[i]);
}
}
}
}
- 후기
한문제에서 조금만 고치니간 금방 풀린다.
LIST
'백준 > C#' 카테고리의 다른 글
| [C#]백준 18352번: 특정 거리의 도시 찾기 (1) | 2023.03.06 |
|---|---|
| [C#]백준 9372번: 상근이의 여행 (0) | 2023.03.06 |
| [C#]백준 24480: 알고리즘 수업 - 깊이 우선 탐색 2 (0) | 2023.03.06 |
| [C#]백준 24444번: 알고리즘 수업 - 너비 우선 탐색 1 (0) | 2023.03.05 |
| [C#]백준 24479번: 알고리즘 수업-깊이 우선 탐색 1 (0) | 2023.03.05 |
