์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- Swfit
- arkit
- ios
- tableView
- CollectionView
- ๋ฐฑ์ค
- ํ๋ก๊ทธ๋๋จธ์ค
- designpattern
- combine
- Kuring
- raywenderlich
- UIKit
- BOJ
- TCA
- RxSwift
- Xcode
- reactorkit
- ํจ์คํธ์บ ํผ์ค
- MVVM
- swift
- rxcocoa
- SwiftUI
- BFS
- node.js
- realm
- Lv2
- Flutter
- SnapKit
- visionOS
- XCTest
- Today
- Total
lgvv98
[Swift] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ณธ๋ฌธ
BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์
โ ์์ ์ด๋ฉด ์ด๊ฑธ ์ด๋ป๊ฒ ํ์ง ์ถ์๋๋ฐ, ์ด์ ๋ ์ฝ๊ฒ ํ์ด๋ผ ์ ์๋ค.
BFS / DFS์ ๊ฒฝ์ฐ์๋ treeํํ๋ก ์ด๋ก ์ ๋ฐฐ์ ์ด์ ๊ทธ๋ํ ํํ๋ฉด ๋์ ํฌ๊ธฐํ๊ณค ํ์๋๋ฐ, ๊ทธ๋ํ๋ ํด๊ฒฐํ ์ ์์๋ค๋..! ์ ๊ธฐํด
๊ทผ๋ฐ ์๋๋ ๋ฌธ์ ํ๋ค๊ฐ ์ด๋ ค์ด๊ฑฐ ์๋๋ฉด ํฌ์คํ ์ํ๋๋ฐ, ์ด๋ ์๊ฐ๋ถํฐ์ธ๊ฐ ๋ชจ๋ ๋ฌธ์ ๋ฅผ ํฌ์คํ ํ๊ณ ์๋ค.
๋๋๋น ํ์ด์ฌ ์ฑ ์์๋ BFS๊ฐ DFS๋ณด๋ค ๋น ๋ฅด๋ค๋ผ๊ณ ํ์์ง๋ง, ์ค์ํํธ์์๋ ๊ตฌํ์ ๋ฐ๋ผ BFS๋ณด๋ค DFS๊ฐ ๋น ๋ฅผ ์ ์๋ค.
์๋์ ๊ธ์ ๋ด๊ฐ DFS / BFS๋ฅผ ๊ตฌํํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
2022.04.02 - [์ฝ๋ฉํ ์คํธ] - [Swift] BOJ 1260 DFS์ BFS
๋๋ ์ฃผ๋ก BFS์ ๊ฒฝ์ฐ removFirst๋ฅผ ์ด์ฉํ๊ธฐ ๋๋ฌธ์, ๋ฐฐ์ด์ write / read ์์ ์ด ๋ค์ด๊ฐ์ ์๊ฐ๋ณต์ก๋์์ ์ํด๋ฅผ ๋ณธ๋ค.
๊ทธ๋์ ๋ฐฑ์ค์์ BFS๋ก ๋ถ๋ฅ๋ ๋ฌธ์ ์์ง๋ง ์ด๋ฒ ๊ตฌํ์์๋ DFS๋ฅผ ์ฌ์ฉํ๋ค. ๋ฌผ๋ก ๋ฌธ์ ์ ๋ฐ๋ผ ๋ค๋ฅด๊ฒ ์ ์ฉํ์ง๋ง!!
โ ์ฝ๋
//https://www.acmicpc.net/problem/11724
import Foundation
struct b11724 {
static func run() {
let info = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var list = [Int: [Int]]()
var keys: Set = Set<Int>()
for _ in 0..<info[1] {
let line = readLine()!.split(separator: " ").map{ Int(String($0))! }
let start = line[0]
let end = line[1]
if list[start] == nil {
list[start] = [end]
keys.insert(start)
} else {
list[start]?.append(end)
}
if list[end] == nil {
list[end] = [start]
keys.insert(end)
} else {
list[end]?.append(start)
}
}
var count = info[0] - keys.count
while !keys.isEmpty {
count += 1
// DFS
var visitedQueue = [Int]()
var needVisitStack = list[keys.first!]!
while !needVisitStack.isEmpty {
let node: Int = needVisitStack.removeLast()
if visitedQueue.contains(node) { continue }
keys.remove(node)
visitedQueue.append(node)
needVisitStack += list[node] ?? []
}
keys.subtract(visitedQueue)
}
print(count)
}
}
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] BOJ 1753 ์ต๋จ๊ฒฝ๋ก (0) | 2022.04.13 |
---|---|
[Swift] ํ๋ก๊ทธ๋๋จธ์ค LV2. ์ ๋ ฅ๋ง์ ๋๋ก ๋๋๊ธฐ (0) | 2022.04.06 |
[Swift] BOJ 1697 ์จ๋ฐ๊ผญ์ง (2์ฐจ์ ๋ฐฐ์ด๋ณด๋ค 1์ฐจ์ ํํ ๋ฐฐ์ด) (0) | 2022.04.05 |
[Swift] BOJ 7576 ํ ๋งํ (0) | 2022.04.03 |
[Swift] BOJ 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ (0) | 2022.04.03 |