[Swift] ํ๋ก๊ทธ๋๋จธ์ค ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง 2 ๋ชจ๋ 0์ผ๋ก ๋ง๋ค๊ธฐ

Problem
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ๋ชจ๋ 0์ผ๋ก ๋ง๋ค๊ธฐ
๊ฐ ์ ์ ๊ฐ์ค์น๊ฐ ๋ถ์ฌ๋ ํธ๋ฆฌ๊ฐ ์ฃผ์ด์ง๋๋ค. ๋น์ ์ ๋ค์ ์ฐ์ฐ์ ํตํ์ฌ, ์ด ํธ๋ฆฌ์ ๋ชจ๋ ์ ๋ค์ ๊ฐ์ค์น๋ฅผ 0์ผ๋ก ๋ง๋ค๊ณ ์ ํฉ๋๋ค. ์์์ ์ฐ๊ฒฐ๋ ๋ ์ ์ ๊ณจ๋ผ์ ํ์ชฝ์ 1 ์ฆ๊ฐ์ํค๊ณ , ๋ค๋ฅธ ํ
programmers.co.kr
Solution
1. 0์ผ๋ก ๋ง๋ค ์ ์๋ ํธ๋ฆฌ์ธ์ง ํ์ธํ๊ธฐ
๊ฐ ๊ฐ์ค์น์ ๋ชจ๋ ํฉ์ด 0์ด๋ผ๋ฉด 0์ผ๋ก ๋ง๋ค ์ ์๋ ํธ๋ฆฌ์ ๋๋ค.
๋ง์ฝ 0์ผ๋ก ๋ง๋ค ์ ์๋ค๋ฉด -1์ ๋ฐํํฉ๋๋ค.
(canMakeZero ํจ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!)
2. ๊ฐ ์ ์ ๋ง๋ค ๋ถ๋ชจ์ ์์์ ์ธํ ํ๊ธฐ
๊ฐ edges์ ์ฐ๊ฒฐ๋ ์ ์ ๋ค์ ์๋ก ๋ถ๋ชจ์ ์์์ผ๋ก ์ค์ ํฉ๋๋ค.
(setChildren ํจ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!)
3. DFS๋ก ๋ฆฌํ ๋ ธ๋ ์ฐพ๊ธฐ
0๋ถํฐ ์์ํด 0๊ณผ ์ฐ๊ฒฐ๋ ์์๋ค ๊ทธ ์์๋ค์ ์์๋ค... ์ ํ์ํด์ ๊ฐ์ฅ ๋ง์ง๋ง ์ ์ ์ ์ฐพ์ต๋๋ค.
๊ฐ์ฅ ๋ง์ง๋ง ์ ์ ๋ถํฐ ๊ทธ ์ ์ ์ ๋ถ๋ชจ.. ์ ์ ์ ๋ถ๋ชจ์ ๋ถ๋ชจ... ์๊ฒ ๊ฐ์ ์ ๋ฌํ๋ฉฐ ๊ฐ์ฅ ์ฒซ๋ฒ์งธ ๋ถ๋ชจ์ธ 0๊น์ง ๊ฐ์ ๋ชจ๋ ์ ๋ฌํฉ๋๋ค.
์ด ๊ณผ์ ์์ ๊ฐ์ ์ ๋ฌํ๋ ํ์๋ฅผ answer ๋ณ์์ ์ ๋๊ฐ์ผ๋ก ๋ํด์ค๋๋ค.
(findLeafNode ํจ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!)
4. answer๋ฅผ ๋ฐํํฉ๋๋ค.
ํ์๋ฅผ ์ ์ฅํ answer๋ฅผ ๋ฐํํด์ค๋๋ค.
Source Code
func solution(_ a:[Int], _ edges:[[Int]]) -> Int64 { | |
//๊ฐ ์ ์ ์ ํด๋นํ๋ ์์๋ค์ ์ ์ฅํด๋์ | |
var children:[[Int]] = Array(repeating: [Int](), count: a.count) | |
//๊ฐ์ค์น ์ ์ฅ | |
var weights = a | |
//์ต์๊ฐ | |
var answer:Int64 = 0 | |
//0์ผ๋ก ๋ง๋ค ์ ์๋ค๋ฉด | |
if canMakeZero(weights: weights) { | |
//๊ฐ ์ ์ ์ ์์๋ค์ ์ธํ ํจ | |
setChilds(edges: edges, children: &children) | |
//dfs๋ก ๊ฐ์ฅ ๋ง์ง๋ง ์์๋ค(๋ฆฌํ ๋ ธ๋)๊น์ง ๋ด๋ ค๊ฐ์ ๊ฐ ๊ฐ์ค์น๋ฅผ ๋ํด์ค | |
findLeafNode(current: 0, parent: 0, children: children, weights: &weights, answer: &answer) | |
//์ ๋ต์ ๋ฐํ | |
return answer | |
} | |
//0์ ๋ง๋ค ์ ์๋ค๋ฉด -1์ ๋ฐํ | |
return -1 | |
} | |
//์์๋ค์ ์ธํ ํจ | |
func setChildren(edges:[[Int]],children:inout [[Int]]) { | |
//๊ฐ ์ ์ ์ ์ฐ๊ฒฐ์ ๋ํ ๊ฐ์ ์ํ | |
for edge in edges { | |
//์ฐ๊ฒฐ๋ ์ ์ ๋ค์ ์๋ก ๋ถ๋ชจ ์์์ผ๋ก ์ค์ ํจ | |
children[edge[0]].append(edge[1]) | |
children[edge[1]].append(edge[0]) | |
} | |
} | |
//dfs๋ก ์ธํ ๋ ๋ฆฌํ ๋ ธ๋๋ฅผ ์ฐพ์์ ์ฐจ๋ก๋ก ๋ํด์ค | |
func findLeafNode(current:Int,parent:Int,children:[[Int]],weights:inout [Int],answer:inout Int64) { | |
//ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ์์๋ค์ ์ํํจ | |
for child in children[current] { | |
//๋ง์ฝ ์ฐ๊ฒฐ๋ ๊ฒ๋ค ์ค ๋ถ๋ชจ๊ฐ ์๋๋ผ๋ฉด | |
if child != parent { | |
//dfs๋ก ๊ทธ ์๋ ์์๋ค๋ก ์ํํจ | |
findLeafNode(current: child, parent: current, children: children,weights: &weights,answer: &answer) | |
} | |
} | |
//๋ถ๋ชจ์ ๊ฐ์ค์น์ ์์์ ๊ฐ์ ๋ํจ | |
weights[parent] += weights[current] | |
//์ต์์น์ ์์๋ค์ ์ ๋๊ฐ์ ๋ํจ | |
answer += Int64(abs(weights[current])) | |
} | |
//0์ ๋ง๋ค ์ ์๋? | |
func canMakeZero(weights:[Int]) -> Bool { | |
//๋ชจ๋ ํฉ์ด 0์ด ๋๋์ง ๋ฐํ | |
return weights.reduce(0,+) == 0 | |
} |
P.S
์ฒ์์ ํธ๋ฆฌ๋ฌธ์ ์ธ์ง ๋ชจ๋ฅด๊ณ ๊ทธ๋ํ ๋ฌธ์ ์ธ ์ค ์๊ณ ์๋ชป ์ ๊ทผํด์ ํ๋ก์ด๋๋ก ํ์ด์ผํ๋...?
๋ผ๋ ์๊ฐ์ ํด์ ์ฝ์ง์ ๋ง์ด ํ๋ค...
๋ ๊ฐ์ฅ ๋ง์ง๋ง๋ถํฐ ์ฐจ๋ก๋๋ก ๊ฐ์ ๋ํด์ฃผ๋ฉด ๋๊ฒ ๊ตฌ๋๋ผ๊ณ ์๊ฐํ๋๋ฐ DFS๋ก ์ฐพ์ ๋ฐฉ๋ฒ์ ๋ชป๋ ์ฌ๋ ค์
์ข ์ค๋๊ฑธ๋ ธ๋ค.