๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

DFS11

[Swift] 2022 KAKAO BLIND RECRUITMENT ์‚ฌ๋ผ์ง€๋Š” ๋ฐœํŒ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์‚ฌ๋ผ์ง€๋Š” ๋ฐœํŒ [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. ํ”Œ๋ ˆ์ด์–ด์˜ ์œ„์น˜์™€ ๊ฒŒ์ž„ ๋๋‚ฌ์„ ๋•Œ ์›€์ง์ธ ํšŸ์ˆ˜์™€ ์Šน์ž๋ฅผ ์•Œ๋ ค์ค„ ๊ตฌ์กฐ์ฒด๋ฅผ ๋งŒ๋“ ๋‹ค. struct Location { var x:Int,y:Int } struct GameResult { var count:Int,isWinnerA:Bool } 2. board์˜ ๊ฐ€์žฅ ์ž๋ฆฌ๋ฅผ 0์œผ๋กœ ๊ฐ์‹ธ์ค€๋‹ค. Index out of range ์˜ค๋ฅ˜๋ฅผ ์‰ฝ๊ฒŒ ํ”ผํ•˜๊ธฐ ์œ„ํ•ด์„œ ์ž…๋‹ˆ๋‹ค. func wrapBoard.. 2022. 1. 20.
[Swift] 2022 KAKAO BLIND RECRUITMENT ์–‘๊ณผ ๋Š‘๋Œ€ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์–‘๊ณผ ๋Š‘๋Œ€ [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ์™„์ „ํƒ์ƒ‰๊ณผ DFS๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. edge๋ฅผ ์ด์šฉํ•ด ๋ถ€๋ชจ์™€ ์ž์‹์„ ์—ฐ๊ฒฐํ•ด์ค๋‹ˆ๋‹ค. func connectEdge(_ edges:[[Int]]) { for edge in edges { if pc[edge[0]] == nil { pc[edge[0]] = [edg.. 2022. 1. 19.
[Swift] 2022 KAKAO BLIND RECRUITMENT ์–‘๊ถ๋Œ€ํšŒ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์–‘๊ถ๋Œ€ํšŒ ๋ฌธ์ œ ์„ค๋ช… ์นด์นด์˜ค๋ฐฐ ์–‘๊ถ๋Œ€ํšŒ๊ฐ€ ์—ด๋ ธ์Šต๋‹ˆ๋‹ค. ๋ผ์ด์–ธ์€ ์ €๋ฒˆ ์นด์นด์˜ค๋ฐฐ ์–‘๊ถ๋Œ€ํšŒ ์šฐ์Šน์ž์ด๊ณ  ์ด๋ฒˆ ๋Œ€ํšŒ์—๋„ ๊ฒฐ์Šน์ „๊นŒ์ง€ ์˜ฌ๋ผ์™”์Šต๋‹ˆ๋‹ค. ๊ฒฐ์Šน์ „ ์ƒ๋Œ€๋Š” ์–ดํ”ผ์น˜์ž…๋‹ˆ๋‹ค. ์นด์นด์˜ค๋ฐฐ ์–‘๊ถ๋Œ€ํšŒ ์šด์˜์œ„์› programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” DFS ๋ฐ ์™„์ „ํƒ์ƒ‰ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. ๊ฐ ์ ์ˆ˜๋งˆ๋‹ค ์ด๊ธธ์ง€ ์งˆ์ง€๋ฅผ ๊ฒฐ์ •ํ•œ๋‹ค. 10์ ๋ถ€ํ„ฐ 1์ ๊นŒ์ง€ ์–ดํ”ผ์น˜๋ฅผ ์ด๊ธธ ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ํŒ๋ณ„ํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์ด๊ธธ ์ˆ˜ ์žˆ๋‹ค๋ฉด ํ•ด๋‹น ์ ์ˆ˜๋ฅผ ์–ป๋Š” ๋ฐฉ๋ฒ•๊ณผ ๊ทธ๋ƒฅ 0๋ฐœ์„ ์ด์„œ ๋‹ค๋ฅธ ์ ์ˆ˜๋ฅผ ์–ป์„ ๋ฐฉ๋ฒ•์„ ํƒํ•ฉ๋‹ˆ๋‹ค. DFS๋ฅผ ์‚ฌ์šฉํ•ด์„œ ์ด๊ธฐ๋Š” ๊ฒฝ์šฐ์™€ ๊ทธ๋ƒฅ 0๋ฐœ์„ ์˜๊ณ  ๋‹ค์Œ ๋‹จ๊ณ„๋กœ ๋„˜์–ด๊ฐˆ ๊ฒฝ์šฐ 2๊ฐ€์ง€๋ฅผ ์žฌ๊ท€ํ•ด์ค๋‹ˆ๋‹ค. func dfs(leftArrow:Int,depth:Int,history:[Int],info:[.. 2022. 1. 19.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์œ„ํด๋ฆฌ ์ฑŒ๋ฆฐ์ง€ ํ”ผ๋กœ๋„ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํ”ผ๋กœ๋„ XX๊ฒŒ์ž„์—๋Š” ํ”ผ๋กœ๋„ ์‹œ์Šคํ…œ(0 ์ด์ƒ์˜ ์ •์ˆ˜๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค)์ด ์žˆ์œผ๋ฉฐ, ์ผ์ • ํ”ผ๋กœ๋„๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋˜์ „์„ ํƒํ—˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, ๊ฐ ๋˜์ „๋งˆ๋‹ค ํƒํ—˜์„ ์‹œ์ž‘ํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ "์ตœ์†Œ ํ•„์š” ํ”ผ๋กœ๋„"์™€ ๋˜ programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋ฐฑํŠธ๋ž˜ํ‚น์œผ๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. (ํ˜น์‹œ ๋ฐฑํŠธ๋ž˜ํ‚น์„ ๋ชจ๋ฅด์‹œ๋Š” ๋ถ„๋“ค์€ ์—ฌ๊ธฐ ์—์„œ ๋ณด๊ณ  ์™€์ฃผ์„ธ์š”!) answer๋ฅผ 0๋ถ€ํ„ฐ ํƒํ—˜์„ ์‹œ์ž‘ํ•ด์ค๋‹ˆ๋‹ค. func solution(_ k:Int, _ dungeons:[[Int]]) -> Int { var answer:Int = 0 explore(dungeons: dungeons, answer: &answer, k:k, count: 0) return answer } ๋˜์ „๋“ค์„ .. 2021. 12. 10.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์œ„ํด๋ฆฌ ์ฑŒ๋ฆฐ์ง€ 9์ฃผ์ฐจ ์ „๋ ฅ๋ง์„ ๋‘˜๋กœ ๋‚˜๋ˆ„๊ธฐ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - 9์ฃผ์ฐจ 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr Solution 1. ์ „์„ ๋ง์˜ ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ connect ์ด์ค‘๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด์„œ ์ €์žฅํ•œ๋‹ค. var connect = Array(repeating: Array(repeating: false, count: n+1), count:n+1) wires.forEach { connect[$0[0]][$0[1]] = true connect[$0[1]][$0[0]] = true } 2. ์—ฐ๊ฒฐ๋œ ์ „์„ ์„ ํ•˜๋‚˜์”ฉ ์ž˜๋ผ๋ณด๋ฉฐ ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ์ฃผ๊ณ  ์ตœ์†Ÿ๊ฐ’๊ณผ ๋น„๊ตํ•ฉ๋‹ˆ๋‹ค. ์šฐ์„  ์ตœ์†Ÿ๊ฐ’์„ .. 2021. 10. 7.
[Swift] 2020 KAKAO INTERNSHIP ๊ฒฝ์ฃผ๋กœ ๊ฑด์„ค Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ฒฝ์ฃผ๋กœ ๊ฑด์„ค [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” DFS๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. ์ž๋™์ฐจ์™€ ์ƒํ•˜์ขŒ์šฐ ๋ฐฉํ–ฅ ๋ชจ๋ธ์„ ๋งŒ๋“ค์–ด์ค€๋‹ค. (ํ•„์ˆ˜๋Š” ์•„๋‹˜) ์ž๋™์ฐจ์— ํ•„์š”ํ•œ x,y,price,prev์™€ ์ƒ.. 2021. 8. 31.
[Algorithm] ๋ฐฑํŠธ๋ž˜ํ‚น(Backtracking)์ด๋ž€? (feat. ์˜ˆ์ œํฌํ•จ) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค N-Queen ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ํ•ด๋‹น ๋ฌธ์ œ๊ฐ€ ๋ฐฑํŠธ๋ž˜ํ‚น ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋Š”๋ฐ์š”. ๊ทธ๋ž˜์„œ ๋ฐฑํŠธ๋ž˜ํ‚น์ด ๋ฌด์—‡์ด๊ณ  ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•ด์„œ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š”์ง€์— ๋Œ€ํ•ด ์ •๋ฆฌํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ๋ฐฑํŠธ๋ž˜ํ‚น์ด๋ž€? ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ „๋ถ€ ๊ณ ๋ คํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ƒํƒœ๊ณต๊ฐ„์„ ํŠธ๋ฆฌ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์„ ๋•Œ ์ ํ•ฉํ•œ ๋ฐฉ์‹์ด๋‹ค. ์ผ์ข…์˜ ํŠธ๋ฆฌ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ  ๋ด๋„ ๋œ๋‹ค. ๋ฐฉ์‹์— ๋”ฐ๋ผ์„œ ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰(Depth First Search, DFS)๊ณผ ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰(Breadth First Search, BFS), ์ตœ์„  ์šฐ์„  ํƒ์ƒ‰(Best First Search/HeuristicSearch)์ด ์žˆ๋‹ค. ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ณ ๋ คํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ๋ผ๋ฉด, DFS๊ฐ€ ๋‚ซ๋‹ค. BFS๋กœ๋„ ๊ตฌํ˜„์ด ๋ฌผ๋ก  ๊ฐ€๋Šฅํ•˜์ง€๋งŒ,.. 2021. 8. 28.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค N-Queen Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - N-Queen ๊ฐ€๋กœ, ์„ธ๋กœ ๊ธธ์ด๊ฐ€ n์ธ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ๋œ ์ฒด์ŠคํŒ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒด์ŠคํŒ ์œ„์˜ n๊ฐœ์˜ ํ€ธ์ด ์„œ๋กœ๋ฅผ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๋„๋ก ๋ฐฐ์น˜ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด์„œ n์ด 4์ธ๊ฒฝ์šฐ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ€ธ์„ ๋ฐฐ์น˜ํ•˜๋ฉด n๊ฐœ์˜ ํ€ธ์€ programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋ฐฑํŠธ๋ž˜ํ‚น(DFS)์œผ๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. ๊ฐ ํ–‰๋งˆ๋‹ค ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ์œ„์น˜๋ฅผ ์ฒดํฌํ•œ๋‹ค. ๊ฐ ํ–‰๋งˆ๋‹ค ํ€ธ์€ ํ•˜๋‚˜์”ฉ๋ฐ–์— ๋ชป๋†“์œผ๋ฏ€๋กœ ํ˜„์žฌ ํ–‰์˜ ์—ด๋“ค์— ๊ณต๊ฒฉํ•  ์ˆ˜ ์žˆ๋Š” ํ€ธ์ด ์žˆ๋Š”์ง€ ์ฒดํฌํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๊ณต๊ฒฉํ•  ์ˆ˜ ์žˆ๋Š” ํ€ธ์ด ์—†๋‹ค๋ฉด ํ˜„์žฌ ์œ„์น˜๋ฅผ history(ํ€ธ์˜ ์œ„์น˜๋ฅผ ์ €์žฅํ•˜๋Š” 2์ฐจ์› ๋ฐฐ์—ด)์— ์ €์žฅํ•ด๋†“๊ณ  ๋‹ค์Œ ํ–‰์œผ๋กœ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ์ง„ํ–‰ํ•˜๋ฉด์„œ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ํ–‰๊นŒ์ง€ ๋„๋‹ฌํ•œ ๊ฒฝ์šฐ๋Š” ๋ฐฐ์น˜ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์ด๋ฏ€๋กœ.. 2021. 8. 28.
[Swift] 2019 ์นด์นด์˜ค ๊ฐœ๋ฐœ์ž ๊ฒจ์šธ ์ธํ„ด์‰ฝ ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž ๊ฐœ๋ฐœํŒ€ ๋‚ด์—์„œ ์ด๋ฒคํŠธ ๊ฐœ๋ฐœ์„ ๋‹ด๋‹นํ•˜๊ณ  ์žˆ๋Š” "๋ฌด์ง€"๋Š” ์ตœ๊ทผ ์ง„ํ–‰๋œ ์นด์นด์˜ค์ด๋ชจํ‹ฐ์ฝ˜ ์ด๋ฒคํŠธ์— ๋น„์ •์ƒ์ ์ธ ๋ฐฉ๋ฒ•์œผ๋กœ ๋‹น์ฒจ์„ ์‹œ๋„ํ•œ ์‘๋ชจ์ž๋“ค์„ ๋ฐœ๊ฒฌํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฐ ์‘๋ชจ์ž๋“ค์„ ๋”ฐ๋กœ ๋ชจ์•„ ๋ถˆ๋Ÿ‰ programmers.co.kr Solution 1. ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž์™€ ์œ ์ € ์•„์ด๋””๋ฅผ ๋น„๊ตํ•œ๋‹ค. func isEqual(userId:String,bannedId:String) -> Bool { if userId.count != bannedId.count { return false } let uid = userId.map{String($0)} let bid = bannedId.map{String($0)} for (i,b) in bid.enumerated() { if b != "*" &.. 2021. 6. 26.
[Algorithm] ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS,Depth-First-Search)์ด๋ž€? (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ‘Ÿ ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์—์„œ ์—„์ฒญ ๋นˆ๋ฒˆํ•˜๊ฒŒ ์ถœ์ œ๋˜๊ณ  ์•Œ์•„๋‘๋ฉด ์ •๋ง ์œ ์šฉํ•œ DFS์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”! DFS๋ž€? "๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์€ ๋งน๋ชฉ์  ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์˜ ํ•˜๋‚˜๋กœ ํƒ์ƒ‰ํŠธ๋ฆฌ์˜ ์ตœ๊ทผ์— ์ฒจ๊ฐ€๋œ ๋…ธ๋“œ๋ฅผ ์„ ํƒํ•˜๊ณ , ์ด ๋…ธ๋“œ์— ์ ์šฉ ๊ฐ€๋Šฅํ•œ ๋™์ž‘์ž ์ค‘ ํ•˜๋‚˜๋ฅผ ์ ์šฉํ•˜์—ฌ ํŠธ๋ฆฌ์— ๋‹ค์Œ ์ˆ˜์ค€์˜ ํ•œ ๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋ฅผ ์ฒจ๊ฐ€ํ•˜๋ฉฐ, ์ฒจ๊ฐ€๋œ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๋ชฉํ‘œ๋…ธ๋“œ์ผ ๋•Œ๊นŒ์ง€ ์•ž์˜ ์ž์‹ ๋…ธ๋“œ์˜ ์ฒจ๊ฐ€ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ด ๊ฐ€๋Š” ๋ฐฉ์‹์ด๋‹ค." - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ด๊ฒŒ ๋ญ”๋ง์ด์•ผ....;;; ์‰ฝ๊ฒŒ ์˜ˆ์ œ๋ฅผ ํ†ตํ•ด์„œ ์„ค๋ช…๋“œ๋ฆฌ๊ฒ ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜ ์‚ฌ์ง„๊ณผ ๊ฐ™์ด ์ง€๊ตฌ ์•ˆ์— ์„ธ ๋‚˜๋ผ๋งŒ ์žˆ๊ณ  ๋ชจ๋“  ๋‚˜๋ผ์™€ ๋‚˜๋ผ์˜ ๋„์‹œ๋“ค์„ ํƒ์ƒ‰ํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์–ด๋–ค ์‚ฌ๋žŒ์€ "๋‚œ ๋จผ์ € ์–ด๋–ค ๋‚˜๋ผ๋“ค์ด ์žˆ๋Š”์ง€ ๋ถ€ํ„ฐ ํ™•์ธํ•˜๊ณ  ๊ทธ ๋‚˜๋ผ ์•ˆ์— ์žˆ๋Š”.. 2021. 6. 5.
[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๊ณผ ์—ฐ๊ฒฐ๋œ .. 2021. 6. 2.
728x90
๋ฐ˜์‘ํ˜•