๐Ÿ“– Problem Solution/Programmers

[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ 2 ๋ชจ๋‘ 0์œผ๋กœ ๋งŒ๋“ค๊ธฐ

Fomagran ๐Ÿ’ป 2021. 6. 2. 11:42
728x90
๋ฐ˜์‘ํ˜•

 

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๋กœ ์ฐพ์„ ๋ฐฉ๋ฒ•์„ ๋ชป๋– ์˜ฌ๋ ค์„œ

 

์ข€ ์˜ค๋ž˜๊ฑธ๋ ธ๋‹ค.

728x90
๋ฐ˜์‘ํ˜•
๋Œ“๊ธ€์ˆ˜0