안녕하세요, 이번 강좌에서는 C++를 이용하여 알고리즘 문제를 해결하는 과정에 대해 알아보겠습니다. 우리는 그래프 탐색을 통해 ‘특정 거리의 도시 찾기’라는 문제를 풀어볼 것입니다. 이 문제는 코딩 테스트에서 자주 등장하는 주제 중 하나로, BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)와 같은 그래프 탐색 기법을 통해 해결할 수 있습니다.
문제 설명
문제의 요구사항은 다음과 같습니다:
N개의 도시가 있다. 각 도시는 서로 연결되어 있으며, 길이 있다. 두 도시 A와 B를 연결하는 도로는 단방향일 수 있다. 도시의 수 N, 도시의 수를 나타내는 간선 M, 그리고 거리 K가 주어졌을 때, 거리 K 를 가지는 도시 번호를 출력하는 프로그램을 작성하시오. 또한, 만약 그러한 도시가 없으면 -1을 출력한다. 두 도시 A와 B를 연결하는 길이 여러 개 있는 경우는 없으며, 모든 도로는 단방향이다.
입력 형식
첫 번째 줄에는 도시의 수 N, 도로의 수 M, 거리 K가 주어진다. 두 번째 줄부터 M개의 줄에는 도로의 정보가 주어지며, 각 도로는 두 개의 정수 A와 B로 주어져 A에서 B로 향하는 단방향 도로가 존재함을 의미한다.
출력 형식
거리 K에 있는 도시의 번호를 출력하고, 만약 그런 도시가 없다면 -1을 출력해야 한다.
예제 입력
4 4 2
1 2
1 3
2 3
2 4
예제 출력
4
문제 해결 과정
우리는 그래프를 이용해 문제를 해결할 것입니다. 각 도시를 정점으로 보고, 도로를 간선으로 생각하여 그래프를 구성합니다. 다음 단계를 통해 문제를 해결해 보겠습니다.
1. 그래프 표현하기
첫번째 단계로, 인접 리스트를 사용하여 그래프를 표현합니다. 인접 리스트는 각 정점에 대해 연결된 정점 리스트를 저장하는 형식입니다. 이렇게 하면 도시 간의 연결 관계를 쉽게 확인할 수 있습니다.
2. BFS를 활용한 탐색
우리는 BFS(너비 우선 탐색) 알고리즘을 사용하여 특정 거리의 도시를 탐색할 것입니다. BFS는 한 정점에서 시작하여 인접한 모든 정점을 레벨별로 탐색할 수 있는 알고리즘으로, 특정 거리에서의 노드를 찾기 적합합니다.
3. 결과 저장 및 처리
거리 K에 해당하는 모든 도시 번호를 수집하고, 이를 출력합니다. 또한, K와 같은 거리를 가지는 도시에 대한 조건이 없을 경우 -1을 출력하도록 설정합니다.
구현 코드
아래는 C++로 구현한 코드입니다. 이 코드를 통해 문제를 해결할 수 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<vector<int>> graph(N + 1);
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
graph[A].push_back(B);
}
vector<int> distance(N + 1, -1);
queue<int> q;
// 시작 도시 1에서 거리 0으로 설정
distance[1] = 0;
q.push(1);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int next : graph[current]) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
q.push(next);
}
}
}
vector<int> result;
for (int i = 1; i <= N; i++) {
if (distance[i] == K) {
result.push_back(i);
}
}
if (result.empty()) {
cout << -1 << endl;
} else {
sort(result.begin(), result.end());
for (int city : result) {
cout << city << endl;
}
}
return 0;
}
결론
이번 강좌에서는 ‘특정 거리의 도시 찾기’ 문제를 통해 그래프 탐색 기법을 배우고, BFS를 활용하여 문제를 해결하는 방법을 살펴보았습니다. 이와 같은 문제는 알고리즘 면접에서 많이 출제되므로, 충분한 연습을 통해 문제 해결 능력을 기르는 것이 중요합니다. 다음 강좌에서는 또 다른 알고리즘 문제를 다루어 보겠습니다. 감사합니다!