안녕하세요! 이번 포스트에서는 자바스크립트 코딩테스트의 하나의 주제로 “케빈 베이컨의 6단계 법칙”에 대해 알아보고, 문제를 해결하는 과정을 상세하게 설명드리겠습니다. 이 강의에서는 알고리즘을 설계하고 구현하는 과정, 그리고 자바스크립트 문법 및 함수를 효율적으로 활용하는 방법에 대해 배워보겠습니다.
1. 케빈 베이컨의 6단계 법칙이란?
케빈 베이컨의 6단계 법칙은 영화 배우들 간의 관계를 설명하는 이론입니다. 이 이론에 따르면, 두 사람 간의 관계는 최대 6단계의 연결을 통해 이루어질 수 있다는 것입니다. 즉, 어떤 배우 A가 배우 B와 관계를 맺고, B가 C와 또 다른 관계를 맺는 식으로 연결되면, A와 C 사이의 관계는 6단계 이내에 있을 것이라는 믿음입니다.
2. 문제 설명
이번 문제는 그래프 이론을 기반으로 한 문제입니다. 주어진 배우 목록과 그들 간의 관계를 통해, 특정한 배우와 다른 배우 간의 연결 고리를 찾고, 몇 단계로 연결되어 있는지를 계산하는 것입니다.
문제 정의
주어진 배우 목록과 그들의 관계를 그래프로 나타내고,
주어진 두 배우 간의 최단 경로를 구하여,
그 간의 단계 수를 반환하는 함수를 작성하세요.
제한 조건:
- 각 배우는 문자열로 표현되며, 두 배우가 함께 출연한 영화에서 직접 연결됩니다.
- 그래프의 간선은 무방향이며, 이 때문에 BFS(너비 우선 탐색)를 사용하여 최단 경로를 찾는 방식을 사용할 수 있습니다.
예제 입력:
actors = [
['A', 'B'],
['B', 'C'],
['C', 'D'],
['D', 'E'],
['A', 'E']
]
startActor = 'A'
targetActor = 'D'
예제 출력:
3 (A -> B -> C -> D)
3. 해결 방법
이 문제를 해결하기 위해서는 다음과 같은 단계로 진행합니다.
3.1. 데이터 구조 선택
우선, 모든 배우들 간의 관계를 저장할 데이터 구조가 필요합니다. 우리는 이 관계를 Map 또는 Object를 사용하여 그래프로 표현할 것입니다. 각 배우는 키가 되고, 그에 해당하는 값은 함께 출연한 배우들의 배열이 됩니다.
3.2. 그래프 구성
주어진 배우 목록을 통해 위에서 선택한 데이터 구조에 배우와 배우 간의 관계를 추가합니다.
3.3. 최단 경로 찾기
BFS 알고리즘을 사용하여 시작 배우와 목표 배우 간의 최단 경로를 찾습니다. BFS는 최단 거리 문제를 해결하는 데 유용한 알고리즘으로, 수준별로 노드를 탐색하기 때문에 최단 경로를 보장합니다.
4. 자바스크립트 구현
이제 위에서 설명한 내용을 바탕으로 자바스크립트 코드로 구현해 보겠습니다.
function findShortestPath(actors, startActor, targetActor) {
// 그래프 생성
const graph = {};
for (const [actorA, actorB] of actors) {
if (!graph[actorA]) graph[actorA] = [];
if (!graph[actorB]) graph[actorB] = [];
graph[actorA].push(actorB);
graph[actorB].push(actorA);
}
// BFS 알고리즘
const queue = [[startActor, 0]];
const visited = new Set();
visited.add(startActor);
while (queue.length > 0) {
const [currentActor, steps] = queue.shift();
// 목표 배우에 도달했을 경우
if (currentActor === targetActor) {
return steps;
}
for (const neighbor of graph[currentActor]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, steps + 1]);
}
}
}
// 연결이 없음
return -1;
}
// 예제 실행
const actors = [['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E'], ['A', 'E']];
const startActor = 'A';
const targetActor = 'D';
console.log(findShortestPath(actors, startActor, targetActor)); // 출력: 3
5. 코드 분석
위 코드를 통해 우리는 주어진 배우 간의 관계를 기반으로 그래프를 구성하고, BFS를 통해 최단 경로를 찾아내는 과정을 구현했습니다. 이 부분을 좀 더 상세히 분석해 보겠습니다.
5.1. 그래프 구현
그래프는 객체 형태로 구성되며, 키는 배우 이름이고, 값은 그와 연결된 배우들의 배열입니다. 우리는 곧바로 양방향 관계를 갱신하여, 서로 연결된 배우를 추가합니다.
5.2. BFS 동작 원리
BFS는 큐를 사용하여 구현되었습니다. 시작 배우를 큐에 추가하고, 방문한 배우는 Set에 추가하여 중복 방문을 피합니다. 큐가 비워질 때까지 반복적으로 탐색을 진행하며, 목표 배우를 찾으면 그간의 단계 수를 반환합니다.
5.3. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(V + E)로, V는 배우의 수, E는 간선의 수입니다. 이로 인해 효율적으로 작동하며, 대규모 데이터에서도 빠른 시간 내에 결과를 도출할 수 있습니다.
6. 결론
이번 포스트에서는 “케빈 베이컨의 6단계 법칙”을 활용한 알고리즘 문제를 해결하는 과정을 살펴보았습니다. 알고리즘 설계, 데이터 구조의 선택, 구현 및 분석까지의 전체 과정을 풀어봤습니다. 이러한 문제는 실제 코딩테스트에서도 빈번하게 출제되므로, 연습을 통해 숙달하는 것이 중요합니다.
앞으로도 다양한 알고리즘과 문제 해결 방법을 다루는 포스트를 계속해서 올리도록 하겠습니다. 항상 코딩 연습을 잊지 마시고, 질문이 있으시면 언제든지 댓글로 남겨주세요!