효과적인 알고리즘 문제풀이를 위해 다양한 문제를 함께 풀어보는 강좌입니다. 오늘 우리가 다룰 문제는 ‘거짓말쟁이가 되긴 싫어’라는 주제를 기반으로 하고 있습니다. 이 문제를 통해 통계적 사고와 조건문, 리스트 처리 기술을 익히게 될 것입니다.
문제 설명
최근에 한 참가자가 날라리로 선발된 결혼식에 참석하게 되었습니다. 그런데 그 결혼식에는 그가 원치 않는 친구가 100명이나 초대되어 있었습니다. 이들은 결혼식에서 자신의 친구가 아닌 타인을 거짓말로 소개할 계획을 세우고 있습니다.
각 친구들은 특정 인원에 대해 ‘나는 A와 B를 알고 있다’ 라고 주장할 수 있습니다. 여러분의 임무는 모든 거짓말을 확인하고서 두 친구들이 같은 사람을 알고 있는지 판별하는 것입니다.
주어진 입력은 친구의 수, 각 친구의 거짓말 정보가 포함됩니다. 여러분은 입력된 정보를 바탕으로 과연 어떤 친구가 거짓말을 하는지를 판단해야 합니다.
입력 예시
5
1 2
2 3
3 4
4 5
1 5
첫 줄에는 친구의 수 N이 주어지고, 이후 N줄에는 각각의 친구가 알고 있는 친구의 번호가 주어집니다.
출력 예시
Yes
두 친구가 서로를 알고 있을 경우 ‘Yes’, 그렇지 않을 경우는 ‘No’를 출력합니다.
문제 접근법
이 문제를 해결하기 위해서는 그래프 탐색 알고리즘을 이용할 수 있습니다. 각각의 친구들을 정점으로 하고, 그들 사이의 관계를 간선으로 표현하여 그래프를 구성합니다. DFS나 BFS와 같은 탐색 방식을 사용하여 두 친구가 서로를 알고 있는지를 확인할 수 있습니다.
기본적인 접근 방법은 친구 관계를 리스트에 저장하고, 주어진 두 친구에 대해 그래프 탐색을 실시하는 것입니다.
코드 구현
아래는 스위프트로 구현한 코드입니다.
import Foundation
func canKnowEachOther(N: Int, friendships: [(Int, Int)], friendA: Int, friendB: Int) -> String {
// 그래프 초기화
var graph = Array(repeating: [Int](), count: N + 1)
// 친구 관계 저장
for (a, b) in friendships {
graph[a].append(b)
graph[b].append(a)
}
// BFS 초기화
var queue = [friendA]
var visited = Array(repeating: false, count: N + 1)
visited[friendA] = true
while !queue.isEmpty {
let current = queue.removeFirst()
// 친구 B를 발견했는가?
if current == friendB {
return "Yes"
}
for neighbor in graph[current] {
if !visited[neighbor] {
visited[neighbor] = true
queue.append(neighbor)
}
}
}
return "No"
}
// 입력 예시
let N = 5
let friendships = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)]
let result = canKnowEachOther(N: N, friendships: friendships, friendA: 1, friendB: 5)
print(result) // "Yes"
코드 설명
위의 코드는 다음과 같은 방식으로 동작합니다:
- 그래프 초기화: 입력 받은 친구 관계를 바탕으로 인접 리스트 형태로 그래프를 초기화합니다.
- BFS 탐색: 주어진 친구 A에서 시작하여 BFS를 실행하면서 친구 B에 도착했는지를 확인합니다. 이미 방문한 친구는 다시 방문하지 않도록 관리합니다.
- 결과 반환: 친구 B를 발견하면 “Yes”를 반환하고, 모든 탐색을 마친 후에도 발견하지 못했을 경우 “No”를 반환합니다.
추가적 고려사항
이 문제의 해결 방법은 기본적인 DFS/BFS 탐색이기 때문에 굉장히 직관적입니다. 하지만 문제의 범위가 증가하게 되면 더 효율적인 방법을 모색해야 할 수도 있습니다. 예를 들어, 친구 수가 많아질 경우 DFS 대신 Union-Find 알고리즘을 적용하는 것이 성능상 유리할 수 있습니다.
만약 더 복잡한 관계나 무작위적 구성의 데이터가 주어진다면 이를 해결하기 위해 다양한 기법(예: Dynamic Programming 옵션 등)을 활용할 수 있습니다. 알고리즘 설계 시 최악의 경우 시간 복잡도와 공간 복잡도를 고려하여 선택하는 것이 매우 중요합니다.