문제: DFS/BFS - 여행경로
| 문제 링크 |
|---|
 |
import Foundation
func solution(_ numbers:[Int], _ target:Int) -> Int {
return 0
}해결한 코드
import Foundation
func solution(_ tickets: [[String]]) -> [String] {
var routes: [String:[String]] = [:]
let ticketCount = tickets.count
for ticket in tickets {
let start = ticket[0], end = ticket[1]
routes[start, default: []].append(end)
}
for key in routes.keys {
routes[key]?.sort() // 조건: 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return함
}
func dfs(_ current: String, _ path: inout [String]) -> Bool {
if path.count == ticketCount + 1 { // 조건: 주어진 항공권은 모두 사용해야 함
return true
}
guard let destinations = routes[current] else { return false } // 다음 목적지가 없다면 돌아가기
for (index, next) in destinations.enumerated() {
routes[current]?.remove(at: index)
path.append(next)
if dfs(next, &path) { // 항공권을 모두 썼는지 체크 & 다음 경로 확인
return true
}
path.removeLast()
routes[current]?.insert(next, at: index)
}
return false
}
var path: [String] = ["ICN"] // 조건: 항상 "ICN" 공항에서 출발
_ = dfs("ICN", &path)
return path
}// 테스트 케이스
let tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
let expected = ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]routesDefault = ["ICN": ["SFO", "ATL"], "SFO": ["ATL"], "ATL": ["ICN", "SFO"]] // ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]
routesSorted = ["ICN": ["ATL", "SFO"], "SFO": ["ATL"], "ATL": ["ICN", "SFO"]] // ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
path = ["ICN", ... ]다른 버전: 출발 공항이 고정되지 않은 경우
import Foundation
func solution(_ tickets:[[String]]) -> [String] {
var routes: [String: [String]] = [:]
var allAirports: Set<String> = []
var destinations: Set<String> = []
// 그래프 생성
for ticket in tickets {
let start = ticket[0], end = ticket[1]
routes[start, default: []].append(end)
allAirports.insert(start)
allAirports.insert(end)
destinations.insert(end)
}
// 도착 공항 리스트 사전순 정렬
for key in routes.keys {
routes[key]?.sort()
}
// DFS 함수
func dfs(_ current: String, _ path: inout [String], _ ticketCount: Int) -> Bool {
// 모든 티켓 사용 완료 시 경로 반환
if path.count - 1 == ticketCount {
return true
}
guard let destinations = routes[current] else { return false }
for (index, next) in destinations.enumerated() {
// 티켓 사용 처리
routes[current]?.remove(at: index)
path.append(next)
// 재귀 호출
if dfs(next, &path, ticketCount) {
return true
}
// 백트래킹: 티켓 복구
path.removeLast()
routes[current]?.insert(next, at: index)
}
return false
}
// 출발 공항 결정
let firstStart = routes.keys.sorted().first ?? tickets[0][0]
var path: [String] = [firstStart]
let ticketCount = tickets.count
// DFS 호출
_ = dfs(firstStart, &path, ticketCount)
return path
}처음에 '문제 조건: "ICN"이 무조건 첫 공항'임을 간과해서 헤맸는데, 출발 공항을 만약 알파벳 순으로 선택한다면 - 즉, 단순히 모든 티켓을 소진하는 게 조건이었다면 - 위와 같은 코드로 해결할 수 있지 않았을까 싶다. 문제 해결에 뛰어들기 전에 반드시 문제 조건을 확실하게 파악하고 접근하자!!!
What I've Learned:
DFS (Depth-First Search) & BFS (Breadth-First Search)
DFS와 BFS는 그래프나 트리를 탐색하는 두 가지 대표적인 알고리즘이다.
1. DFS (Depth-First Search: 깊이 우선 탐색)
DFS는 한 경로를 끝까지 탐색한 뒤, 다른 경로를 탐색하는 방식.
즉, 가능한 한 깊이 내려가서 탐색을 진행한다.
동작 방식:
- 루트 노드에서 시작함.
- 자식 노드 중 하나를 선택해 계속 내려감.
- 더 이상 갈 곳이 없으면 되돌아가며 다른 경로를 탐색함.
특징:
- 구현 방식: 재귀 함수 또는 스택을 사용.
- 적용 사례: 경로 탐색, 퍼즐 해결, 그래프의 연결성 확인 등.
DFS 구현
이진 트리 구조 정의
class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(value: Int, left: TreeNode? = nil, right: TreeNode? = nil) {
self.value = value
self.left = left
self.right = right
}
}DFS (재귀 기반)
func dfsRecursive(_ node: TreeNode?) {
guard let node = node else { return }
print(node.value, terminator: " ") // 현재 노드 방문
dfsRecursive(node.left) // 왼쪽 자식 탐색
dfsRecursive(node.right) // 오른쪽 자식 탐색
}DFS (스택 기반)
func dfsIterative(_ root: TreeNode?) {
guard let root = root else { return }
var stack: [TreeNode] = [root] // 스택을 사용
while !stack.isEmpty {
let node = stack.removeLast() // 스택의 마지막 노드 방문
print(node.value, terminator: " ")
if let right = node.right { // 오른쪽 자식을 스택에 추가
stack.append(right)
}
if let left = node.left { // 왼쪽 자식을 스택에 추가
stack.append(left)
}
}
}DFS 실행 예제
let root = TreeNode(value: 1,
left: TreeNode(value: 2, left: TreeNode(value: 4), right: TreeNode(value: 5)),
right: TreeNode(value: 3)
)
// DFS 실행
print("DFS (Recursive):")
dfsRecursive(root) // 출력: 1 2 4 5 3
print("\nDFS (Iterative):")
dfsIterative(root) // 출력: 1 2 4 5 32. BFS (Breadth-First Search: 너비 우선 탐색)
BFS는 같은 레벨의 모든 노드를 탐색한 뒤, 다음 레벨로 이동하는 방식.
즉, 가까운 노드부터 탐색하며 점점 멀리 있는 노드로 이동함.
동작 방식:
- 루트 노드에서 시작.
- 큐(Queue)를 이용하여 현재 노드의 자식 노드를 모두 추가함.
- 큐에서 노드를 꺼내며 방문하고, 자식 노드를 큐에 추가함.
특징:
- 구현 방식: 큐(Queue)를 사용.
- 적용 사례: 최단 경로 탐색, 레벨 단위 탐색 등.
BFS 구현 (Swift)
이진 트리 구조 정의
class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(value: Int, left: TreeNode? = nil, right: TreeNode? = nil) {
self.value = value
self.left = left
self.right = right
}
}BFS 함수
func bfs(_ root: TreeNode?) {
guard let root = root else { return }
var queue: [TreeNode] = [root] // 큐를 사용
while !queue.isEmpty {
let node = queue.removeFirst() // 큐의 첫 번째 노드 방문
print(node.value, terminator: " ")
if let left = node.left { // 왼쪽 자식을 큐에 추가
queue.append(left)
}
if let right = node.right { // 오른쪽 자식을 큐에 추가
queue.append(right)
}
}
}BFS 실행 예제
let root = TreeNode(value: 1,
left: TreeNode(value: 2, left: TreeNode(value: 4), right: TreeNode(value: 5)),
right: TreeNode(value: 3)
)
// BFS 실행
print("BFS:")
bfs(root) // 출력: 1 2 3 4 53. DFS와 BFS의 차이점 비교 (이진 트리 기준)
| 특징 | DFS | BFS |
|---|---|---|
| 탐색 방식 | 깊이 우선 (한 경로를 끝까지 탐색) | 너비 우선 (같은 레벨을 먼저 탐색) |
| 구현 자료구조 | 스택 (재귀 또는 명시적 스택) | 큐 |
| 탐색 순서 | 루트 → 왼쪽 → 오른쪽 | 루트 → 같은 레벨 순서 |
| 적용 사례 | 경로 찾기, 퍼즐 | 최단 경로, 레벨별 탐색 |
4. 트리 예제 (DFS와 BFS 결과 비교)
트리 구조
1
/ \
2 3
/ \
4 5탐색 결과
- DFS (깊이 우선 탐색):
1 → 2 → 4 → 5 → 3 - BFS (너비 우선 탐색):
1 → 2 → 3 → 4 → 5
DFS는 깊이 중심으로 탐색하고, BFS는 레벨 중심으로 탐색하는 차이를 확인할 수 있다.
inout 키워드
Swift에서 &를 사용하여 함수 외부에 있는 변수를 수정하는 것은 inout 키워드를 사용하는 경우이다. inout은 함수 내부에서 매개변수를 직접 수정할 수 있도록 허용하며, Swift의 기본값 전달 방식(값 복사)을 참조 방식으로 바꿔준다.
1. inout의 동작 원리
기본 매개변수 전달 방식
Swift에서는 함수의 매개변수를 기본적으로 값 복사 방식으로 전달한다. 즉, 함수 내부에서 매개변수를 변경해도 외부 변수에는 영향을 주지 않는다.
func increment(_ number: Int) {
var number = number
number += 1
}
var myNumber = 5
increment(myNumber)
print(myNumber) // 5 (변경되지 않음)inout 매개변수
inout을 사용하면 함수 내부에서 매개변수를 직접 수정할 수 있다. 이 경우, 매개변수는 함수 내부와 외부에서 동일한 참조를 공유한다.
func increment(_ number: inout Int) {
number += 1
}
var myNumber = 5
increment(&myNumber)
print(myNumber) // 6 (변경됨)2. inout의 특징
-
참조 전달
inout을 사용하면 함수 내부에서 매개변수를 수정할 때, 원본 변수도 함께 수정된다.
-
매개변수 앞에
&사용inout매개변수를 함수에 전달할 때는 반드시&를 붙여서 호출해야 한다. 이는 "참조를 전달한다"는 것을 명시적으로 나타낸다.
-
inout은 값의 복사본을 사용- 함수가 실행되는 동안 매개변수의 복사본을 사용하고, 함수가 종료되면 변경된 값을 원래 변수에 반영한다.
- 따라서 함수 내부에서 매개변수에 다른 값을 할당해도 문제없이 작동한다.
-
리터럴 값 사용 불가
inout매개변수는 변수만 전달할 수 있습니다. 상수(let)나 리터럴 값은 사용할 수 없다.
var myNumber = 5 increment(&myNumber) // 가능 increment(5) // 오류: 리터럴 값을 inout으로 전달 불가
3. inout의 사용 사례
1) Swap 함수
두 변수의 값을 교환하는 함수는 inout 없이 구현하기 어렵다.
func swapValues(_ a: inout Int, _ b: inout Int) {
let temp = a
a = b
b = temp
}
var x = 10
var y = 20
swapValues(&x, &y)
print(x, y) // 20, 102) 배열 수정
배열을 inout 매개변수로 전달하여 함수 내부에서 직접 수정할 수 있다.
func reverseFirstTwo(_ array: inout [Int]) {
guard array.count >= 2 else { return }
let temp = array[0]
array[0] = array[1]
array[1] = temp
}
var numbers = [1, 2, 3, 4]
reverseFirstTwo(&numbers)
print(numbers) // [2, 1, 3, 4]3) 문자열 수정
문자열도 inout을 사용하여 직접 수정할 수 있다.
func appendExclamation(_ text: inout String) {
text += "!"
}
var myText = "Hello"
appendExclamation(&myText)
print(myText) // "Hello!"4. 주의점
-
참조 타입과의 차이점
inout은 값 타입에서 참조를 전달할 때 유용하다.- 클래스와 같은 참조 타입은
inout없이도 함수 내부에서 값을 변경하면 원본에 반영된다.
-
스코프 내 안전성
inout매개변수는 함수가 실행되는 동안 값을 복사해 사용하며, 함수가 끝날 때 복사본이 원래 변수로 다시 복사된다.- 따라서 함수 내부에서 변수에 새로운 값을 할당해도 안전하다.
-
성능 고려
inout을 사용할 때 실제로 값을 복사해 사용하기 때문에, 대규모 데이터를 전달할 경우 성능에 영향을 미칠 수 있다.
5. inout을 DFS에서 사용하는 이유
DFS와 같은 알고리즘에서는 현재 경로를 저장하는 배열이나 현재 상태를 나타내는 변수를 함수 호출 간에 지속적으로 수정해야 한다. 이때 inout을 사용하면 호출 스택을 통해 현재 상태를 공유하고 백트래킹을 간단하게 구현할 수 있다.
func dfs(_ current: String, _ path: inout [String]) {
path.append(current)
// ... 탐색 로직 ...
path.removeLast() // 백트래킹
}
var path: [String] = []
dfs("ICN", &path)요약
inout은 함수 내부에서 외부 변수의 값을 수정할 수 있게 해준다.- 함수 호출 시
&를 붙여 참조를 전달한다. - DFS, 백트래킹, 스왑 등 외부 변수의 상태를 지속적으로 변경해야 하는 알고리즘에서 매우 유용하다.
Reciprocity lies in knowing enough