C# 코딩테스트 강좌, 특정 거리의 도시 찾기

안녕하세요, 여러분. 오늘은 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를 통해 거리 기반 탐색을 하는 과정에서 그래프 데이터 구조와 탐색 알고리즘의 중요성을 느낄 수 있었기를 바랍니다.
다음 강좌에서는 더욱 다양한 문제를 함께 해결해 보도록 하겠습니다.