๐Ÿงก๋ฌธ์ œ ์„ค๋ช…

2์ง„ ํŠธ๋ฆฌ ๋ชจ์–‘ ์ดˆ์›์˜ ๊ฐ ๋…ธ๋“œ์— ๋Š‘๋Œ€์™€ ์–‘์ด ํ•œ ๋งˆ๋ฆฌ์”ฉ ๋†“์—ฌ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ดˆ์›์˜ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๊ฐ ๋…ธ๋“œ๋ฅผ ๋Œ์•„๋‹ค๋‹ˆ๋ฉฐ ์–‘์„ ๋ชจ์œผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•  ๋•Œ ๋งˆ๋‹ค ํ•ด๋‹น ๋…ธ๋“œ์— ์žˆ๋˜ ์–‘๊ณผ ๋Š‘๋Œ€๊ฐ€ ๋‹น์‹ ์„ ๋”ฐ๋ผ์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ๋Š‘๋Œ€๋Š” ์–‘์„ ์žก์•„๋จน์„ ๊ธฐํšŒ๋ฅผ ๋…ธ๋ฆฌ๊ณ  ์žˆ์œผ๋ฉฐ, ๋‹น์‹ ์ด ๋ชจ์€ ์–‘์˜ ์ˆ˜๋ณด๋‹ค ๋Š‘๋Œ€์˜ ์ˆ˜๊ฐ€ ๊ฐ™๊ฑฐ๋‚˜ ๋” ๋งŽ์•„์ง€๋ฉด ๋ฐ”๋กœ ๋ชจ๋“  ์–‘์„ ์žก์•„๋จน์–ด ๋ฒ„๋ฆฝ๋‹ˆ๋‹ค. ๋‹น์‹ ์€ ์ค‘๊ฐ„์— ์–‘์ด ๋Š‘๋Œ€์—๊ฒŒ ์žก์•„๋จนํžˆ์ง€ ์•Š๋„๋ก ํ•˜๋ฉด์„œ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์ˆ˜์˜ ์–‘์„ ๋ชจ์•„์„œ ๋‹ค์‹œ ๋ฃจํŠธ ๋…ธ๋“œ๋กœ ๋Œ์•„์˜ค๋ ค ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์œ„ ๊ทธ๋ฆผ์˜ ๊ฒฝ์šฐ(๋ฃจํŠธ ๋…ธ๋“œ์—๋Š” ํ•ญ์ƒ ์–‘์ด ์žˆ์Šต๋‹ˆ๋‹ค) 0๋ฒˆ ๋…ธ๋“œ(๋ฃจํŠธ ๋…ธ๋“œ)์—์„œ ์ถœ๋ฐœํ•˜๋ฉด ์–‘์„ ํ•œ๋งˆ๋ฆฌ ๋ชจ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์Œ์œผ๋กœ 1๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•˜๋ฉด ๋‹น์‹ ์ด ๋ชจ์€ ์–‘์€ ๋‘ ๋งˆ๋ฆฌ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ๋ฐ”๋กœ 4๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•˜๋ฉด ๋Š‘๋Œ€ ํ•œ ๋งˆ๋ฆฌ๊ฐ€ ๋‹น์‹ ์„ ๋”ฐ๋ผ์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์•„์ง์€ ์–‘ 2๋งˆ๋ฆฌ, ๋Š‘๋Œ€ 1๋งˆ๋ฆฌ๋กœ ์–‘์ด ์žก์•„๋จนํžˆ์ง€ ์•Š์ง€๋งŒ, ์ดํ›„์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋ชจ๋“  ๋…ธ๋“œ(2, 3, 6, 8๋ฒˆ)์—๋Š” ๋Š‘๋Œ€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด์–ด์„œ ๋Š‘๋Œ€๊ฐ€ ์žˆ๋Š” ๋…ธ๋“œ๋กœ ์ด๋™ํ•œ๋‹ค๋ฉด(์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐ”๋กœ 6๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•œ๋‹ค๋ฉด) ์–‘ 2๋งˆ๋ฆฌ, ๋Š‘๋Œ€ 2๋งˆ๋ฆฌ๊ฐ€ ๋˜์–ด ์–‘์ด ๋ชจ๋‘ ์žก์•„๋จนํž™๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ๋Š” 0๋ฒˆ, 1๋ฒˆ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜์—ฌ ์–‘์„ 2๋งˆ๋ฆฌ ๋ชจ์€ ํ›„, 8๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•œ ํ›„(์–‘ 2๋งˆ๋ฆฌ ๋Š‘๋Œ€ 1๋งˆ๋ฆฌ) ์ด์–ด์„œ 7๋ฒˆ, 9๋ฒˆ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋ฉด ์–‘ 4๋งˆ๋ฆฌ ๋Š‘๋Œ€ 1๋งˆ๋ฆฌ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ด์ œ 4๋ฒˆ, 6๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•˜๋ฉด ์–‘ 4๋งˆ๋ฆฌ, ๋Š‘๋Œ€ 3๋งˆ๋ฆฌ๊ฐ€ ๋˜๋ฉฐ, ์ด์ œ 5๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์–‘์„ ์ตœ๋Œ€ 5๋งˆ๋ฆฌ ๋ชจ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ฐ ๋…ธ๋“œ์— ์žˆ๋Š” ์–‘ ๋˜๋Š” ๋Š‘๋Œ€์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด info, 2์ง„ ํŠธ๋ฆฌ์˜ ๊ฐ ๋…ธ๋“œ๋“ค์˜ ์—ฐ๊ฒฐ ๊ด€๊ณ„๋ฅผ ๋‹ด์€ 2์ฐจ์› ๋ฐฐ์—ด edges๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ฌธ์ œ์— ์ œ์‹œ๋œ ์กฐ๊ฑด์— ๋”ฐ๋ผ ๊ฐ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ๋ชจ์„ ์ˆ˜ ์žˆ๋Š” ์–‘์€ ์ตœ๋Œ€ ๋ช‡ ๋งˆ๋ฆฌ์ธ์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


๐Ÿ’›์ œํ•œ์‚ฌํ•ญ

  • 2 โ‰ค info์˜ ๊ธธ์ด โ‰ค 17
    • info์˜ ์›์†Œ๋Š” 0 ๋˜๋Š” 1 ์ž…๋‹ˆ๋‹ค.
    • info[i]๋Š” i๋ฒˆ ๋…ธ๋“œ์— ์žˆ๋Š” ์–‘ ๋˜๋Š” ๋Š‘๋Œ€๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
    • 0์€ ์–‘, 1์€ ๋Š‘๋Œ€๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
    • info[0]์˜ ๊ฐ’์€ ํ•ญ์ƒ 0์ž…๋‹ˆ๋‹ค. ์ฆ‰, 0๋ฒˆ ๋…ธ๋“œ(๋ฃจํŠธ ๋…ธ๋“œ)์—๋Š” ํ•ญ์ƒ ์–‘์ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • edges์˜ ์„ธ๋กœ(ํ–‰) ๊ธธ์ด = info์˜ ๊ธธ์ด - 1
    • edges์˜ ๊ฐ€๋กœ(์—ด) ๊ธธ์ด = 2
    • edges์˜ ๊ฐ ํ–‰์€ [๋ถ€๋ชจ ๋…ธ๋“œ ๋ฒˆํ˜ธ, ์ž์‹ ๋…ธ๋“œ ๋ฒˆํ˜ธ] ํ˜•ํƒœ๋กœ, ์„œ๋กœ ์—ฐ๊ฒฐ๋œ ๋‘ ๋…ธ๋“œ๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
    • ๋™์ผํ•œ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ค‘๋ณตํ•ด์„œ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
    • ํ•ญ์ƒ ํ•˜๋‚˜์˜ ์ด์ง„ ํŠธ๋ฆฌ ํ˜•ํƒœ๋กœ ์ž…๋ ฅ์ด ์ฃผ์–ด์ง€๋ฉฐ, ์ž˜๋ชป๋œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ๋Š” ์—†์Šต๋‹ˆ๋‹ค.
    • 0๋ฒˆ ๋…ธ๋“œ๋Š” ํ•ญ์ƒ ๋ฃจํŠธ ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค.

๐Ÿ’š์ž…์ถœ๋ ฅ ์˜ˆ

infoedgesresult
[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

๐Ÿ’™์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

๋ฌธ์ œ์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

์ฃผ์–ด์ง„ ์ž…๋ ฅ์€ ๋‹ค์Œ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

0๋ฒˆ - 2๋ฒˆ - 5๋ฒˆ - 1๋ฒˆ - 4๋ฒˆ - 8๋ฒˆ - 3๋ฒˆ - 7๋ฒˆ ๋…ธ๋“œ ์ˆœ์œผ๋กœ ์ด๋™ํ•˜๋ฉด ์–‘ 5๋งˆ๋ฆฌ ๋Š‘๋Œ€ 3๋งˆ๋ฆฌ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ 6๋ฒˆ, 9๋ฒˆ ๋…ธ๋“œ๋กœ ์ด๋™ํ•˜๋ฉด ์–‘ 5๋งˆ๋ฆฌ, ๋Š‘๋Œ€ 5๋งˆ๋ฆฌ๊ฐ€ ๋˜์–ด ์–‘์ด ๋ชจ๋‘ ์žก์•„๋จนํžˆ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๋Š‘๋Œ€์—๊ฒŒ ์žก์•„๋จนํžˆ์ง€ ์•Š๋„๋ก ํ•˜๋ฉด์„œ ์ตœ๋Œ€๋กœ ๋ชจ์„ ์ˆ˜ ์žˆ๋Š” ์–‘์€ 5๋งˆ๋ฆฌ์ž…๋‹ˆ๋‹ค.


๐Ÿ’œ์ œํ•œ์‹œ๊ฐ„ ์•ˆ๋‚ด

์ •ํ™•์„ฑ ํ…Œ์ŠคํŠธ : 10์ดˆ


๐ŸคŽ๋‚˜์˜ ํ’€์ด

function solution(info, edges) {
    // ์ •๋‹ต ๋ณ€์ˆ˜
    let result = 0
    // ์—ฐ๊ฒฐ๋œ ๊ธธ์„ ์ƒ์„ฑํ•จ
    const paths = Array.from({length: info.length}, () => [])
    for(let i = 0 ; i < edges.length ; i ++) {
        const [s, e] = edges[i]
        paths[s].push(e)
    }
    function dfs(curNode, canReach, wolf, sheep) {
        
        // ๋ฐฉ๋ฌธ ๊ฐ€๋Šฅํ•œ ๊ณณ ๋ณต์‚ฌ
        const curReach = [...canReach]
        
        // ํ˜„์žฌ ์œ„์น˜ํ•œ ๊ณณ์˜ ์ธ๋ฑ์Šค๊ฐ’
        const curIdx = curReach.indexOf(curNode)
        
        // ํ˜„์žฌ ๋…ธ๋“œ์˜ ๊ฐ’์ด ๋Š‘๋Œ€์ธ์ง€ ์–‘์ธ์ง€ ๊ฒ€์‚ฌ
        if(info[curNode]) {
            wolf++
        } else {
            sheep++
        }
        
        // ์–‘์˜ ์ˆ˜๊ฐ€ ์ตœ๋Œ€์ธ์ง€ ๊ฒ€์‚ฌ
        result = Math.max(result, sheep)
        
        // ์–‘์ด ๋Š‘๋Œ€์—๊ฒŒ ์žก์•„๋จนํžŒ๋‹ค๋ฉด
        if(wolf === sheep) return
        
        // ๋ฐฉ๋ฌธ ๋ชฉ๋ก์— ํ˜„์žฌ ์œ„์น˜์—์„œ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์žฅ์†Œ ์ถ”๊ฐ€
        curReach.push(...paths[curNode])
        // ํ˜„ ์œ„์น˜ ์ œ๊ฑฐ
        curReach.splice(curIdx, 1)
        
        // ๋ฐฉ๋ฌธ์ด ๊ฐ€๋Šฅํ•œ ๊ณณ dfs ํƒ์ƒ‰
        for (const nextNode of curReach) {
            dfs(nextNode, curReach, wolf, sheep);
        }
    }
    dfs(0, [0], 0, 0)
    return result
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€