안녕하세요, 여러분. 오늘은 C#을 활용하여 “특정 거리의 도시 찾기” 문제를 해결하는 방법에 대해 알아보겠습니다. 이 문제는 코딩테스트에서 종종 출제되는 그래프와 BFS(너비 우선 탐색) 알고리즘을 활용한 문제입니다. 그러므로 이 강좌를 통해 그래프 이론과 알고리즘에 대한 이해를 높이는데 큰 도움이 될 것입니다.
문제 설명
주어진 조건을 기반으로 한 문제를 소개합니다.
문제:
N개의 도시가 있고, M개의 양방향 도로가 존재합니다. 각 도시는 1부터 N까지 번호가 매겨져 있으며, 두 도시 A와 B를 연결하는 도로가 있을 때는 A와 B를 연결하는 도로의 길이는 항상 1로 간주합니다. 여러분은 특정 도시 X와 거리 K를 주어질 때, 거리 K인 도시들을 모두 출력해야 합니다.
입력 형식:
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 K, 시작 도시 X가 주어진다.
이후 M개의 줄에 걸쳐서 각각의 도로가 연결하는 두 도시가 주어진다.
출력 형식:
거리 K인 도시의 번호를 오름차순으로 출력한다.
만약 그런 도시가 없다면 -1을 출력한다.
입력 예시
4 4 2 1 1 2 1 3 2 3 2 4
출력 예시
4
문제 분석
이 문제를 해결하기 위해서는 그래프를 표현하고 탐색하는 방법이 필요합니다.
각 도시는 정점, 도로는 간선으로 표현할 수 있습니다.
우리는 BFS 또는 DFS 알고리즘을 사용하여 특정 거리를 찾아야 합니다.
이 문제의 경우 거리 K를 찾으므로 BFS가 더 적합합니다. 왜냐하면 BFS는 가까운 노드부터 탐색하기 때문에 거리 개념을 그대로 활용할 수 있기 때문입니다.
문제 해결 과정
1단계: 데이터 구조 정의
먼저, 도시와 도로를 표현하기 위해서 리스트와 큐를 사용할 것입니다.
– 리스트는 각 도시와 연결된 도로를 저장합니다.
– 큐는 BFS를 수행할 때 필요한 데이터 구조입니다.
2단계: 그래프 생성
도시와 도로 정보를 입력으로 받아서 인접 리스트를 생성합니다.
이 때, 데이터를 1 인덱스부터 사용하기 위해 크기를 N + 1로 설정합니다.
3단계: BFS 구현
BFS 함수를 구현하여 출발 도시 X에서 시작합니다.
거리가 K인 도시를 찾아서 결과를 저장합니다.
4단계: 결과 출력
결과 리스트를 정렬하고 출력합니다.
만약 거리가 K인 도시가 없다면 -1을 출력합니다.
C# 코드 구현
다음은 주어진 문제를 해결하기 위한 C# 코드입니다.
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
static List[] graph;
static bool[] visited;
static List result;
public static void Main(string[] args)
{
// 입력 받기
string[] input = Console.ReadLine().Split(' ');
int N = int.Parse(input[0]); // 도시의 수
int M = int.Parse(input[1]); // 도로의 수
int K = int.Parse(input[2]); // 거리
int X = int.Parse(input[3]); // 시작 도시
// 그래프 초기화
graph = new List[N + 1];
for (int i = 1; i <= N; i++)
{
graph[i] = new List();
}
// 도로 정보 입력
for (int i = 0; i < M; i++)
{
input = Console.ReadLine().Split(' ');
int a = int.Parse(input[0]);
int b = int.Parse(input[1]);
graph[a].Add(b);
graph[b].Add(a);
}
// BFS 및 결과 생성
visited = new bool[N + 1];
result = new List();
BFS(X, 0, K);
// 결과 출력
result.Sort();
if (result.Count == 0)
{
Console.WriteLine(-1);
}
else
{
foreach (int city in result)
{
Console.WriteLine(city);
}
}
}
static void BFS(int start, int distance, int K)
{
Queue> queue = new Queue>();
queue.Enqueue(new Tuple(start, distance));
visited[start] = true;
while (queue.Count > 0)
{
var current = queue.Dequeue();
int currentCity = current.Item1;
int currentDistance = current.Item2;
// 이미 K의 도시를 찾은 경우
if (currentDistance == K)
{
result.Add(currentCity);
continue;
}
// 인접 도시 탐색
foreach (var neighbor in graph[currentCity])
{
if (!visited[neighbor])
{
visited[neighbor] = true;
queue.Enqueue(new Tuple(neighbor, currentDistance + 1));
}
}
}
}
}
코드 설명
위의 C# 코드를 통해 문제를 해결하는 과정을 간략히 설명하겠습니다.
- 데이터 입력: 첫 줄에서 도시 수, 도로 수, 거리 K, 시작 도시 X 값을 읽고, M개의 도로 정보를 입력받습니다.
- 그래프 구성: 도시를 정점으로, 도로를 간선으로 표현하기 위해 인접 리스트를 구성합니다.
- BFS 알고리즘 구현: Queue를 사용하여 BFS를 실행하고 각 도시까지의 거리를 계산합니다.
- 결과 출력: 정렬된 결과를 반환하며, 거리 K와 일치하는 도시가 없을 경우 -1을 출력합니다.
마무리
이번 강좌에서는 “특정 거리의 도시 찾기” 문제를 C#을 활용하여 해결하는 방법을 알아보았습니다.
BFS를 통해 거리 기반 탐색을 하는 과정에서 그래프 데이터 구조와 탐색 알고리즘의 중요성을 느낄 수 있었기를 바랍니다.
다음 강좌에서는 더욱 다양한 문제를 함께 해결해 보도록 하겠습니다.
적절한 자료구조의 선택 또한 성능 향상에 도움이 됩니다.