Problem
Solution
ํด๋น ๋ฌธ์ ๋ BFS ํน์ ๋ค์ต์คํธ๋ผ๋ฅผ ์ด์ฉํ์ฌ ํ์ด์ผ ํ๋ ๋ฌธ์ ์ ๋๋ค.
1. ํ์ฌ ๊ฒฝ๋ก์ ์ต๋ intensity์ ํ์ฌ ์ง์ ์ ์ ๋ณด๋ฅผ ๊ฐ๋ Node๋ฅผ ๋ง๋ค์ด ์ค๋ค.
struct Node {
let current: Int
let maxIntensity: Int
}
2. ํ์ํ ๋ณ์๋ค์ ์ธํ ํด ์ค๋ค.
answer: ๊ฐ์ฅ ์ ์ intensity์ ์ฐ๋ด์ฐ๋ฆฌ์ ๊ฐ์ ์ ์ฅํ ๋ณ์
connection: path์ ์ฐ๊ฒฐ๋ ์ ๋ณด๋ฅผ ์ ์ฅํ ๋ณ์
summitDic: ์ฐ๋ด์ฐ๋ฆฌ๋ฅผ ์ ์ฅํ ๋์ ๋๋ฆฌ
gateDic: ๊ฒ์ดํธ๋ฅผ ์ ์ฅํ ๋์ ๋๋ฆฌ
bfsQueue: bfs๋ฅผ ์งํํ ๋ Node๋ฅผ ๋ด์ ํ
intensities: ๊ฐ ์ง์ ์ ์ต๋ intensity๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
var answer: [Int] = [Int.max,Int.max]
var connection: [Int:[[Int]]] = [:]
var summitDic: [Int:Bool] = [:]
var gateDic: [Int:Bool] = [:]
var bfsQueue: [Node] = []
var intensities: [Int] = Array(repeating: Int.max, count: n+1)
3. summit, gate, path๋ฅผ ์ธํ ํด ์ค๋ค.
for summit in summits {
summitDic[summit] = true
}
for gate in gates {
gateDic[gate] = true
}
for path in paths {
connection[path[0],default:[]].append([path[1],path[2]])
connection[path[1],default:[]].append([path[0],path[2]])
}
4. gate๋ง๋ค bfs๋ก ํ์ํ๋ค.
bfsQueue์ ํด๋น ๊ฒ์ดํธ ์ ๋ณด๋ฅผ ๋ฃ๊ณ bfs๋ก ํ์ํด ์ค๋ค.
bfsQueue๊ฐ ๋ชจ๋ ์์ด์ง ๋๊น์ง checkNextNode๋ก ๋ค์ ์ง์ ์ผ๋ก ์ด๋ํ ํ์๊ฐ ์๋์ง ํ์ธํด ์ค๋ค.
for gate in gates {
bfsQueue.append(Node(current: gate, maxIntensity: -1))
bfs()
}
func bfs() {
while !bfsQueue.isEmpty {
let first = bfsQueue.removeFirst()
checkNextNode(first)
}
}
5. ํ์ฌ ์ง์ ๊ณผ ์ฐ๊ฒฐ๋ ์ง์ ์ค ํ์ํ ํ์๊ฐ ์๋์ง๋ฅผ ์ฒดํฌํ๋ค.
๋จผ์ ํด๋น ๋ ธ๋๊ฐ ์ฐ๋ด์ฐ๋ฆฌ๋ผ๋ฉด ์ด๋ฏธ ๋ชฉํ์ ๋์ฐฉํ ๊ฒ์ด๋ฏ๋ก ํ์ํ์ง ์์๋ ๋๋ค.
(์นด์นด์ค ํด์ค์ ์ฐธ๊ณ ํ๋ฉด ์ด์ฐจํผ ์๋ณต์ด๋ ์ฐ๋ด์ฐ๋ฆฌ๊น์ง ๊ฐ๋ ๊ฒ์ด๋ ์ต๋ intensity๋ ๋๊ฐ์ผ๋ฏ๋ก ์ฐ๋ด์ฐ๋ฆฌ๋ก ๋จ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ ๊ฒ๋ง ์ฒดํฌํ๋ฉด ๋๋ค.)
๋ํ ํด๋น ์ง์ ์ ์ต๋์น๋ณด๋ค ํ์ฌ ๋ ธ๋์ ์ต๋์น๊ฐ ์ ๋ต์ด ๋ ์ ์์ผ๋ฏ๋ก ํ์์ ์ค๋จํ๋ค.
func checkNextNode(_ node: Node) {
if summitDic[node.current] != nil || node.maxIntensity > intensities[node.current] {
return
}
...
์ ๋ ๊ฒฝ์ฐ๊ฐ ๋ชจ๋ ์๋๋ผ๋ฉด ์ด์ ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ ธ๋ ์ค gate๊ฐ ์๋ ๋ ธ๋๋ค ํ์ํ๋ค.
๋จผ์ ํ์ฌ ๊ฒฝ๋ก์ ๊ฐ์ฅ ์ต๋ intensity์ ๋ค์์ผ๋ก ์ด์ด์ง intensity๋ฅผ ๋น๊ตํด maxIntensity๋ฅผ ์ ํ๋ค.
๋ง์ฝ maxIntensity๊ฐ ํด๋น ์ง์ ์ ์ต๋ intensity๋ณด๋ค ์ ๋ค๋ฉด ํด๋น ์ง์ ์ intensity๋ฅผ maxIntensity๋ก ๊ฐฑ์ ํด ์ฃผ๊ณ bfsQueue์ ํด๋น ์ ๋ณด๋ฅผ ๋ฃ์ด์ค๋ค.
๊ทธ ๋ค์ updateAnswer๋ก ์ ๋ต๋ ๊ฐฑ์ ํด ์ฃผ๋๋ฐ ๋ฐ์์ ์ค๋ช ํ๊ฒ ๋ค.
...
for next in connection[node.current,default:[]] where gateDic[next[0]] == nil {
let maxIntensity = max(node.maxIntensity,next[1])
if maxIntensity < intensities[next[0]] {
updateAnswer(next[0], maxIntensity)
intensities[next[0]] = maxIntensity
bfsQueue.append(Node(current: next[0], maxIntensity:maxIntensity))
}
}
}
6. maxIntensity์ ์ ๋ณด๋ก answer๋ฅผ ๊ฐฑ์ ํด ์ค๋ค.
๋ง์ฝ ํด๋น ์ง์ ์ด ์ฐ๋ด์ฐ๋ฆฌ๊ณ answer์ ์ต์๊ฐ๋ณด๋ค ์ ๋ค๋ฉด ํด๋น ์ง์ (index)์ maxIntensity๋ก ๊ฐฑ์ ํด ์ค๋ค.
๋ง์ฝ answer์ ์ต๋๊ฐ๊ณผ maxIntensity๊ฐ ๊ฐ๋ค๋ฉด ์ฐ๋ด์ฐ๋ฆฌ์ ์ง์ ์ด ๋ ๋ฎ์ ๊ฒ์ผ๋ก ๊ฐฑ์ ํด ์ค๋ค.
func updateAnswer(_ index: Int,_ maxIntensity: Int) {
if summitDic[index] != nil {
if maxIntensity == answer[1] {
answer[0] = min(answer[0],index)
} else if maxIntensity < answer[1] {
answer = [index,maxIntensity]
}
}
}
7. answer๋ฅผ ๋ฐํํ๋ค.
return answer
Result
Source Code
struct Node {
let current: Int
let maxIntensity: Int
}
func solution(_ n:Int, _ paths:[[Int]], _ gates:[Int], _ summits:[Int]) -> [Int] {
var answer: [Int] = [Int.max,Int.max]
var connection: [Int:[[Int]]] = [:]
var summitDic: [Int:Bool] = [:]
var gateDic: [Int:Bool] = [:]
var bfsQueue: [Node] = []
var intensities: [Int] = Array(repeating: Int.max, count: n+1)
for summit in summits {
summitDic[summit] = true
}
for gate in gates {
gateDic[gate] = true
}
for path in paths {
connection[path[0],default:[]].append([path[1],path[2]])
connection[path[1],default:[]].append([path[0],path[2]])
}
func checkNextNode(_ node: Node) {
if summitDic[node.current] != nil || node.maxIntensity > intensities[node.current] {
return
}
for next in connection[node.current,default:[]] where gateDic[next[0]] == nil {
let maxIntensity = max(node.maxIntensity,next[1])
if maxIntensity < intensities[next[0]] {
updateAnswer(next[0], maxIntensity)
intensities[next[0]] = maxIntensity
bfsQueue.append(Node(current: next[0], maxIntensity:maxIntensity))
}
}
}
func bfs() {
while !bfsQueue.isEmpty {
let first = bfsQueue.removeFirst()
checkNextNode(first)
}
}
for gate in gates {
bfsQueue.append(Node(current: gate, maxIntensity: -1))
bfs()
}
func updateAnswer(_ index: Int,_ maxIntensity: Int) {
if summitDic[index] != nil {
if maxIntensity == answer[1] {
answer[0] = min(answer[0],index)
} else if maxIntensity < answer[1] {
answer = [index,maxIntensity]
}
}
}
return answer
}
P.S
์ฒ์์ ๊ทธ๋ฅ DFS๋ก ๊ฒฝ๋ก๋ฅผ ํ๋ฒ ํ์ํ ๋ค์ ์ต์ intensity๋ฅผ ์ฐพ์์ผ์ง ํ๋๋ฐ ์ด๊น์์ด ์๊ฐ ์ด๊ณผ๊ฐ ๋์๋ค.
๋ค์ ์๊ฐํด ๋ณด๋๊น BFS๋ก ํด๋น ๊ฒฝ๋ก๋ฅผ ํ์ํ๋ฉด์ ์ต๋๊ฐ๋ณด๋ค ์ ๋ค๋ฉด ํ์์ ์งํํ๊ณ ์๋๋ผ๋ฉด ํ์์ ํ์ง ์์์ค๋ ๋๋ค.
๋ gate์์ ์ถ๋ฐํ์ฌ gate๋ก ๋์ฐฉํ ์์ ํด๋น ์ต์ intensity๋ฅผ ๊ฐฑ์ ํ๋ ์์ผ๋ก ํ๋๋ ์๊ฐ ์ด๊ณผ๊ฐ ๋์์ ์นด์นด์ค ํด์ค์ ๋ณด๋๊น
์ฐ๋ด์ฐ๋ฆฌ๊น์ง ์๋ณต์ผ๋ก ํ์ํ๋ ์ฐ๋ด์ฐ๋ฆฌ๊น์ง ๋จ๋ฐฉํฅ์ผ๋ก ํ์ํ๋ maxIntensity๋ ๋๊ฐ์ผ๋ฏ๋ก ์ฐ๋ด์ฐ๋ฆฌ๋ฅผ ๋ง๋๊ธฐ๊น์ง์ ๊ฒฝ๋ก๋ง ํ์ํ๋ฉด ๋๋ค.
์์ ๋ฆฟ์ฝ๋ ๋ฌธ์ ๋ค๋ง ํ๋ค๊ฐ ์ค๋๋ง์ ํ๋ก๊ทธ๋๋จธ์ค ๋ฌธ์ ๋ฅผ ํธ๋๊น ๋ฌธ์ ๋ฅผ ์ฝ๊ณ ํด์ํ๋ ๊ฒ๋ ์๊ฐ์ด ๊ฑธ๋ ธ๊ณ ๋ณต์กํ ์๊ฐ ์ด๊ณผ ๋ฃฐ๋ ์งํค๊ธฐ๊ฐ ๊น๋ค๋ก์ ๋ค...
'๐ Problem Solution > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] 2022 KAKAO TECH INTERNSHIP ์ฝ๋ฉ ํ ์คํธ ๊ณต๋ถ (0) | 2022.08.26 |
---|---|
[Swift] 2022 KAKAO TECH INTERNSHIP ๋ ํ ํฉ ๊ฐ๊ฒ ๋ง๋ค๊ธฐ (0) | 2022.08.24 |
[Swift] 2022 KAKAO TECH INTERNSHIP ์ฑ๊ฒฉ ์ ํ ๊ฒ์ฌํ๊ธฐ (1) | 2022.08.23 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค ์ซ์์ ํํ (0) | 2022.04.11 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค ๊ฐ์ ์ซ์๋ ์ซ์ด (0) | 2022.04.11 |
๋๊ธ