[๋ฐฑ์ค] ๋ฐ์ด๋ฌ์ค 2606๋ฒ
์ฒ์์ผ๋ก ๋ธ๋ก๊ทธ์์ ๋ฐฑ์ค ๋ฌธ์ ๋ฅผ ํฌ์คํ ํ๋ ค๊ณ ๋ง์๋จน์์ ๋, ๋ฐฑ์ค ๋ฌธ์ ๋ฅผ ํ ๋์ ๊ฒฝํ์ด ๋ค์ ๋ ์ฌ๋์ต๋๋ค. ์์ ์๋ ์ฃผ๋ก ํ๋ก๊ทธ๋๋จธ์ค ๋ฌธ์ ๋ง ํธ๋ ๊ฒฝํฅ์ด ์์๊ธฐ ๋๋ฌธ์, ๋ฐฑ์ค์์ ๋ฌธ์ ๋ฅผ ํ ๋๋ ์ ๋ ฅ๊ฐ์ `readLine()`์ ์ฌ์ฉํด ๋ฐ๊ณ ๊ฐ์ ํ์ฉํ๋ ๊ฒ์ด ์ฝ์ง ์์์ต๋๋ค. ๋๋ก๋ ์ด๋ป๊ฒ ํด์ผ ํ ์ง ๋ง๋งํ ์๊ฐ๋ ์์์ต๋๋ค.
ํ์ง๋ง ์ง๊ธ๊น์ง์ ๊ฒฝํ์ ํตํด ์ด ๋ถ๋ถ์ ์ ์ ์ต์ํด์ง๋ ๊ฒ์ด ์ค์ํ๋ค๋ ๊ฒ์ ์๊ฒ ๋์์ต๋๋ค. ๋ค์ํ ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๋ฉด์ ์ฒ์๋ถํฐ ํจ์จ์ ์ด๊ณ Swift ์ธ์ด์ ๊ฐ์ ์ ์ด๋ฆด ์ ์๋ ๋ฐฉ๋ฒ์ ๋ํด ๊ณ ๋ฏผํ๊ฒ ๋์์ต๋๋ค.
๊ทธ๋์ ๋ฌธ์ ํ์ด๋ฅผ ์ค๋นํ๋ฉด์ ๋ฐฑ์ค๊ณผ ํ๋ก๊ทธ๋๋จธ์ค ๋ฌธ์ ๋ฅผ ๋ฒ๊ฐ์๊ฐ๋ฉฐ ํ์ด๋ณด๊ณ ์๋ค ๋ณด๋ ์ค๋ ฅ์ด ์ ์ฐจ์ ์ผ๋ก ๋์ด๋๊ณ ์๋ค๋ ๋๋์ ๋ฐ์์ต๋๋ค. ์ด๋ฌํ ๊ฒฝํ์ ๋ฐํ์ผ๋ก ๋ธ๋ก๊ทธ์ ๋ฐฑ์ค ๋ฌธ์ ๋ฅผ ๋ค๋ฃจ๋ ํฌ์คํ
์ ์์ฑํ๋ ค๊ณ ํฉ๋๋ค. ๐
์์ผ๋ก๋ ๊ณ์ํด์ ๋ค์ํ ๋ฌธ์ ๋ฅผ ๋์ ํ๋ฉฐ ์ค๋ ฅ์ ํฅ์์ํฌ ์์ ์ด๋ฉฐ ๐ช ๋ธ๋ก๊ทธ๋ฅผ ํตํด ๋ค๋ฅธ ์ฌ๋๋ค๊ณผ ๊ฒฝํ์ ๊ณต์ ํ๋ ๊ฒ๋ ์ข์ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค.
1. ๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/2606
๋ฌธ์
์ ์ข ๋ฐ์ด๋ฌ์ค์ธ ์ ๋ฐ์ด๋ฌ์ค๋ ๋คํธ์ํฌ๋ฅผ ํตํด ์ ํ๋๋ค. ํ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํจํฐ์ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด 7๋์ ์ปดํจํฐ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ์. 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ์ ๋ฐ์ด๋ฌ์ค๋ 2๋ฒ๊ณผ 5๋ฒ ์ปดํจํฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒ๊ณผ 6๋ฒ ์ปดํจํฐ๊น์ง ์ ํ๋์ด 2, 3, 5, 6 ๋ค ๋์ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค. ํ์ง๋ง 4๋ฒ๊ณผ 7๋ฒ ์ปดํจํฐ๋ 1๋ฒ ์ปดํจํฐ์ ๋คํธ์ํฌ์์์ ์ฐ๊ฒฐ๋์ด ์์ง ์๊ธฐ ๋๋ฌธ์ ์ํฅ์ ๋ฐ์ง ์๋๋ค
์ด๋ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค. ์ปดํจํฐ์ ์์ ๋คํธ์ํฌ ์์์ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ปดํจํฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ปดํจํฐ์ ์๋ 100 ์ดํ์ด๊ณ ๊ฐ ์ปดํจํฐ์๋ 1๋ฒ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋งค๊ฒจ์ง๋ค. ๋์งธ ์ค์๋ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ ์์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด์ด์ ๊ทธ ์๋งํผ ํ ์ค์ ํ ์์ฉ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ์ ๋ฒํธ ์์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ์ ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ
7
6
1 2
2 3
1 5
5 2
5 6
4 7
์ ๋ต : 4
2. ์ฝ๋
let count = Int(readLine()!)! //์ฒซ ๋ฒ์งธ ์ค์ ์ปดํจํฐ์ ์
let pairs = Int(readLine()!)! //๋์งธ ์ค์ ์ปดํจํฐ ์์ ์
var graph : [Int : [Int]] = [:]
for i in 0..<pairs{ // for in ๋ฌธ์ ์ด์ฉํ์ฌ ์
๋ ฅ๋ฐ๋ pairs ์๋งํผ ๋ฐ๋ณต์ ๋๋ ค ๋ค๋ฅธ ๊ฐ๋ค์ ๋ฐ์์ฃผ๊ธฐ
let input = readLine()!.split(separator: " ").map { Int(String($0))! } // ๊ณต๋ฐฑ ๊ธฐ์ค ์๋ผ ๋ฐฐ์ด ๋ง๋ค๊ธฐ
let key = input[0]
let value = input[1]
// ์ ๋ฐฉํฅ ๋๋ค ๋ฃ๊ธฐ
if var temp = graph[key] {
temp.append(value)
graph[key] = temp
} else {
graph[key] = [value]
}
if var temp = graph[value] {
temp.append(key)
graph[value] = temp
} else {
graph[value] = [key]
}
}
print(bfs(graph: graph))
func bfs(graph: [Int: [Int]]) -> Int{
// ์ค๋ณต ๋ฐฉ์ง
var visited = Set<Int>()
var queue = [1]
visited.insert(1) // ๋ฏธ๋ฆฌ ๋ฃ๊ธฐ
while !queue.isEmpty{
let currentNode = queue.removeFirst() // ํ์ํ ๋
ธ๋ ๋นผ๊ธฐ ํ ์ฒซ ๋ฒ์งธ์์
if let temp = graph[currentNode] { // ํ์ฌ ํ์ํ๋ ๋
ธ๋ ์ธ์ ๋
ธ๋๋ค ํ์
for node in temp{ // ์ธ์ ๋
ธ๋๋ค ์ค์์ ๋ฐฉ๋ฌธํ ๋
ธ๋ ์๋์ง ํ์ธ
if visited.contains(node){
continue
}
visited.insert(node) // ์์ผ๋ฉด ๋ฐฉ๋ฌธํ๊ณ ํ์ ๋๊ธฐ ์ํค๊ธฐ
queue.append(node)
}
}
}
return visited.count - 1
}
3. ์ฝ๋ ์ค๋ช
์ฝ๋ฉ ํ
์คํธ๋ฅผ ์ค๋นํ๋ฉด์ BFS ๊ด๋ จ ๋ฌธ์ ๋ฅผ ์ฒ์์ผ๋ก ์ ํ๊ฒ ๋ ๋ฌธ์ ์์ต๋๋ค. ๐
๊ทธ๋ํ ๊ด๋ จํด์๋ ๋์ฑ ๊ณต๋ถํ๊ณ ์ ๋ฆฌ๋ฅผ ํ ๋ค์์ ๋ธ๋ก๊ทธ์ ๋ค๋ฅธ ์นดํ
๊ณ ๋ฆฌ์ ํฌ์คํ
ํด์ผ ํ ๊ฑฐ ๊ฐ์ต๋๋คใ
ใ
// 1๋ฒ
if var temp = graph[key] {
temp.append(value)
graph[key] = temp
} else {
graph[key] = [value]
}
// 2๋ฒ
if var temp = graph[value] {
temp.append(key)
graph[value] = temp
} else {
graph[value] = [key]
}
์ด ๋ถ๋ถ์ ์ ๊ฐ ์ฒ์ ๋ฌธ์ ๋ฅผ ํ ๋ ์ค์ํ ๋ถ๋ถ์ ๋๋ค. ์ฒ์์๋ 1๋ฒ ์ฝ๋๋ง ์์ฑํ๊ณ 2๋ฒ ์ฝ๋๋ฅผ ์์ฑํ์ง ์์์ต๋๋ค.
๊ทธ๋์ ๊ทธ๋ํ์ ๋ฐฉํฅ์ฑ์ ๋ํด ์ ๋๋ก ๊นจ๋ซ์ง ๋ชปํ์ต๋๋ค.
1๋ฒ๊ณผ 2๋ฒ์ ๊ฐ๋จํ ํด์ํ์๋ฉด
var graph: [Int: [Int]] = [:]
์ ์ฝ๋์์ ์ ๊ฐ ๋ง๋ ๊ทธ๋ํ์ ๊ตฌ์กฐ๋ ๋์
๋๋ฆฌ ํํ๋ก ๋์ด ์์ผ๋ฉฐ, key ๊ฐ์ Int ํ์ด๊ณ / value ๊ฐ์ [Int] ๋ฐฐ์ด๋ก ๊ตฌ์ฑ๋์ด ์์ต๋๋ค. ์ด๋ ๊ฒ ๋ง๋ ์ด์ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ฌ๋ฌ ๊ฐ์ ๋ค๋ฅธ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ์ ์๊ธฐ ๋๋ฌธ์ [Int]๋ฅผ ๋ง๋ค์ด 1๋ฒ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ๋ค์ ๊ฐ๋ค์ ์ ์ฅํ๋ ค๊ณ ํ์ต๋๋ค.
1๋ฒ ์ฝ๋์์์ if var temp = graph[key] ๋ถ๋ถ์ ๋ฐ๋ณต๋ฌธ์ ๋๋ฉด์ graph[key] ๊ฐ์ด ์๋ค๋ฉด ๊ทธ ๊ฐ์ ์์๋ก temp ๊ฐ์ผ๋ก ๊ฐ์ ธ์ ์๋ก์ด ๊ฐ์ธ value๋ฅผ appendํ์ฌ ๋ค์ ํด๋นํ๋ graph[key] ๊ฐ์ ๋ฃ์ด์ฃผ๋ ๊ฒ์
๋๋ค.
๋ง์ฝ graph[key]์ด ์๋ค๋ฉด ๊ทธ๋๋ก graph[key] = [value] ๊ฐ์ ๋ฃ์ด ๋ค์ ์์๋ก ๋์ด๊ฐ๋๋ค.
์ง๊ธ ์ด ๊ณผ์ ์ 1๋ฒ ์ฝ๋๋ง ์ด๋ฆฐ๋ค๋ฉด ์ด ๊ทธ๋ํ์ ๋ฐฉํฅ์ ๋จ๋ฐฉํฅ์
๋๋ค.
์ฌ๊ธฐ์ ์ ์ค์๊ฐ ๋์์ต๋๋ค. ๋ฌธ์ ์์๋ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์
1 -> 2 ๊ด๊ณ๋ผ๋ฉด 2 -> 1 ๋ ๋น์ฐํ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํฉ๋๋ค. ํ์ง๋ง 1๋ฒ๋ง ์ด๋ฆด ๊ฒฝ์ฐ์๋ ์ฐ๊ฒฐ์ด ๋๊ฒจ ์์ด์ ์ ๋์ ???!์ผ๋ก ์ ๋ต์ ๋งํ์ง ๋ชปํฉ๋๋ค.
๊ทธ๋์ 2๋ฒ ์ฝ๋๋ฅผ ์ถ๊ฐํ๋ ์ด์ ๋ ์๋ฐฉํฅ ๊ทธ๋ํ๋ก ๋ง๋ค๊ธฐ ์ํด์์
๋๋ค. key์ value์ ๊ฐ์ ์์น๋ฅผ ๋ฐ๊ฟ์ ์ ์ฅํด ์ค์ผ๋ก์จ ์๋ฐฉํฅ ๊ด๊ณ๋ฅผ ํํํ์์ต๋๋ค.
์ฃผ์ด์ง ์ฝ๋์์๋ BFS๋ฅผ ํ์ฉํ์ฌ ๊ทธ๋ํ๋ฅผ ํ์ํ๋ ๊ณผ์ ์ ๊ตฌํํ์์ต๋๋ค.
1. ๋ฐ๋ณต๋ฌธ์ ํตํด ๊ทธ๋ํ๋ฅผ ๊ตฌ์ฑํ ํ, bfs ๋ฉ์๋์ ๊ทธ๋ํ๋ฅผ ์ ๋ฌํฉ๋๋ค.
2. ๋ฐฉ๋ฌธํ ๋
ธ๋๋ค์ ์ ์ฅํ๊ธฐ ์ํด visited๋ผ๋ Set์ ์์ฑํฉ๋๋ค. ์ด Set์ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ค์ ๊ฐ์ ์ ์ฅํ์ฌ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ํ์ธํ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค.
3. Queue์ธ queue ๋ฐฐ์ด์ ์์ฑํ์ฌ ์์์ ์ผ๋ก 1์ ๋ฃ์ต๋๋ค. ๋ฌธ์ ์์ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค๊ณ ๋์ด ์๊ธฐ ๋๋ฌธ์
๋๋ค. ๋ํ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ฅผ ์ฒดํฌํ๊ธฐ ์ํด visited์๋ ์ด๊ธฐ์ 1์ ๋ฃ์ด์ค๋๋ค.
4. while ๋ฌธ์ ํตํด Queue๊ฐ ๋น์ด์์ง ์์ ๋๊น์ง ๋ฐ๋ณตํฉ๋๋ค. ์ฌ๊ธฐ์ Queue๋ FIFO(First-In, First-Out)์ ๊ฐ๋
์ ํ์ฉํฉ๋๋ค. ์ฆ, ๋จผ์ ๋ค์ด์จ ๋
ธ๋๋ถํฐ ์ฐจ๋ก๋๋ก ํ์ํฉ๋๋ค.
5. ๋ฐ๋ณต๋ฌธ ์์์๋ Queue์์ ํ์ฌ ๋
ธ๋ ๊ฐ์ ๊บผ๋ด๊ณ , ํด๋น ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ค์ ํ์ธํฉ๋๋ค. ์ด๋, ์ ๋ฌ๋ฐ์ ๊ทธ๋ํ์ธ graph์์ ํ์ฌ ๋
ธ๋์ ๊ฐ์ key๋ก ๊ฐ์ง๋ ๋ฐฐ์ด์ ๊ฐ์ ธ์ต๋๋ค.
6. ๊ฐ์ ธ์จ ๋ฐฐ์ด์ for-in ๋ฐ๋ณต๋ฌธ์ ํตํด ์ฐจ๋ก๋๋ก ํ์ธํฉ๋๋ค. ๋ง์ฝ ํ์ฌ ํ์ธํ๋ ๋
ธ๋๊ฐ ์ด๋ฏธ visited ์ ํฌํจ๋์ด ์๋ค๋ฉด ๋ค์ ์์๋ก ๋์ด๊ฐ๋๋ค. ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๋
ธ๋์ด๋ฏ๋ก ๋ค๋ฅธ ์์
์ ํ ํ์๊ฐ ์์ต๋๋ค. ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ์๋ ํด๋น ๋
ธ๋๋ฅผ queue ์ ๋ฃ๊ณ , visited ์๋ ๊ฐ์ ๋ฃ์ด์ค๋๋ค. ์ด๋ ๊ฒ ํจ์ผ๋ก์จ ๊ฐ์ผ๋ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ค์ ํ์ํ ์ ์์ต๋๋ค.
7. ์ฐ๊ฒฐ๋ ์ปดํจํฐ๊ฐ ๊ณ์ ์๋ค๋ฉด while ๋ฌธ์ ๊ณ์ ๋ฐ๋ณตํ๊ฒ ๋๊ณ , visited์๋ ๊ฐ์ผ๋ ์ปดํจํฐ๋ค์ ๊ฐ๋ค์ด ์ ์ฅ๋ฉ๋๋ค.
8. while๋ฌธ์ ๋ชจ๋ ๋๊ณ ๋๋ฉด queue ๋ฐฐ์ด ์์ ๊ฐ์ด ์๋ค๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค. ์ด๋ ๋ ์ด์ ๊ฐ์ผ๋ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ๊ฐ ์๋ค๋ ์๋ฏธ์
๋๋ค. ๋ฐ๋ผ์ ๊ฒฐ๊ณผ ๊ฐ์ผ๋ก ๋ฐฉ๋ฌธํ visited์ ์์ ๊ฐ์์ -1์ ํ ๊ฐ์ ๋ฐํํฉ๋๋ค. 1๋ฒ ์ปดํจํฐ๋ถํฐ ์์ํ๊ธฐ ๋๋ฌธ์ 1์ ๋บ ๊ฐ์ด ์ ๋ต์ด ๋ฉ๋๋ค.
๊ธ์ ์ฐ๋ค ๋ณด๋ ์ข ๋ ์์ธํ๊ฒ ์ค๋ช
ํ๊ณ ์ถ์ ๋ง์์ ๊ธ์ด ๊ธธ์ด์ก์ต๋๋คใ
ใ
๐ฎ
์ ๋ ์ฒ์์ ํ ๋๋ ์ ๋ง ์ดํด๊ฐ ์ ๊ฐ๊ณ ์ฌ๋ฌ ๋ค๋ฅธ ๋ธ๋ก๊ทธ๋ฅผ ๋ฐฉ๋ฌธํด ๊ฐ๋ฉด์ ์ ๊ฐ๊ฐ ๋ค๋ฅธ ์ฝ๋์ง๋ง ๋ฌธ์ ๋ฅผ ํธ๋ ๋ฐฉ์์ ๋ํด์ ๊ณ์ ์๊ฐํด ๋ดค๋ ๊ฑฐ ๊ฐ์ต๋๋ค. ๋ฌผ๋ก ์ ๋ ๋ค๋ฅธ ์ ํ์ ๋ฌธ์ ๋ฅผ ํ๊ฒ ๋๋ค๋ฉด ์ฒ์๋ถํฐ ์ด ์ ๋๋ก ํด์ค์ด ์๋ ๊ฑฐ ๊ฐ์ต๋๋คใ
ใ
;;
๊ทธ๋๋ ํน์๋ ์ด ๋ฌธ์ ์ ๋ํด์ ์ ๊ฐ ์๊ฐํ๋ ๋ถ๋ถ์ด ํ์ํ ๋ถ์ด ๊ณ์ค ์๋ ์์ผ๋ ๊ฐ๋ณ๊ฒ ์ฝ์ด์ฃผ์๊ณ ๋ค๋ฅธ ๋ฌธ์ ๋ค๋ ํ์ดํ
ํ์ญ์์คแแ๐