์ž๋ฃŒ๊ตฌ์กฐ & ์•Œ๊ณ ๋ฆฌ์ฆ˜

[๋ฐฑ์ค€] ๋ฐ”์ด๋Ÿฌ์Šค 2606๋ฒˆ

๊ธฐ๊ฐ€์ •ํ›ˆ 2023. 6. 3. 22:22

 

 

์ฒ˜์Œ์œผ๋กœ ๋ธ”๋กœ๊ทธ์—์„œ ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํฌ์ŠคํŒ…ํ•˜๋ ค๊ณ  ๋งˆ์Œ๋จน์—ˆ์„ ๋•Œ, ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ์˜ ๊ฒฝํ—˜์ด ๋‹ค์‹œ ๋– ์˜ฌ๋ž์Šต๋‹ˆ๋‹ค. ์˜ˆ์ „์—๋Š” ์ฃผ๋กœ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๋ฌธ์ œ๋งŒ ํ‘ธ๋Š” ๊ฒฝํ–ฅ์ด ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์—, ๋ฐฑ์ค€์—์„œ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ๋Š” ์ž…๋ ฅ๊ฐ’์„ `readLine()`์„ ์‚ฌ์šฉํ•ด ๋ฐ›๊ณ  ๊ฐ’์„ ํ™œ์šฉํ•˜๋Š” ๊ฒƒ์ด ์‰ฝ์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค. ๋•Œ๋กœ๋Š” ์–ด๋–ป๊ฒŒ ํ•ด์•ผ ํ• ์ง€ ๋ง‰๋ง‰ํ•œ ์ˆœ๊ฐ„๋„ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.


ํ•˜์ง€๋งŒ ์ง€๊ธˆ๊นŒ์ง€์˜ ๊ฒฝํ—˜์„ ํ†ตํ•ด ์ด ๋ถ€๋ถ„์— ์ ์  ์ต์ˆ™ํ•ด์ง€๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์–‘ํ•œ ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ณด๋ฉด์„œ ์ฒ˜์Œ๋ถ€ํ„ฐ ํšจ์œจ์ ์ด๊ณ  Swift ์–ธ์–ด์˜ ๊ฐ•์ ์„ ์‚ด๋ฆด ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๊ณ ๋ฏผํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ค€๋น„ํ•˜๋ฉด์„œ ๋ฐฑ์ค€๊ณผ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๋ฌธ์ œ๋ฅผ ๋ฒˆ๊ฐˆ์•„๊ฐ€๋ฉฐ ํ’€์–ด๋ณด๊ณ  ์žˆ๋‹ค ๋ณด๋‹ˆ ์‹ค๋ ฅ์ด ์ ์ฐจ์ ์œผ๋กœ ๋Š˜์–ด๋‚˜๊ณ  ์žˆ๋‹ค๋Š” ๋Š๋‚Œ์„ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฌํ•œ ๊ฒฝํ—˜์„ ๋ฐ”ํƒ•์œผ๋กœ ๋ธ”๋กœ๊ทธ์— ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ๋‹ค๋ฃจ๋Š” ํฌ์ŠคํŒ…์„ ์ž‘์„ฑํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๐Ÿ˜
์•ž์œผ๋กœ๋„ ๊ณ„์†ํ•ด์„œ ๋‹ค์–‘ํ•œ ๋ฌธ์ œ๋ฅผ ๋„์ „ํ•˜๋ฉฐ ์‹ค๋ ฅ์„ ํ–ฅ์ƒ์‹œํ‚ฌ ์˜ˆ์ •์ด๋ฉฐ ๐Ÿ’ช  ๋ธ”๋กœ๊ทธ๋ฅผ ํ†ตํ•ด ๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค๊ณผ ๊ฒฝํ—˜์„ ๊ณต์œ ํ•˜๋Š” ๊ฒƒ๋„ ์ข‹์€ ๋ฐฉ๋ฒ•์ด๋ผ๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

 


1. ๋ฌธ์ œ ๋งํฌ 

 

2606๋ฒˆ: ๋ฐ”์ด๋Ÿฌ์Šค

์ฒซ์งธ ์ค„์—๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋Š” 100 ์ดํ•˜์ด๊ณ  ๊ฐ ์ปดํ“จํ„ฐ์—๋Š” 1๋ฒˆ ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ ์Œ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด

www.acmicpc.net

https://www.acmicpc.net/problem/2606

 

๋ฌธ์ œ

์‹ ์ข… ๋ฐ”์ด๋Ÿฌ์Šค์ธ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ๋„คํŠธ์›Œํฌ๋ฅผ ํ†ตํ•ด ์ „ํŒŒ๋œ๋‹ค. ํ•œ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋ชจ๋“  ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด 7๋Œ€์˜ ์ปดํ“จํ„ฐ๊ฐ€ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•˜์ž. 1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” 2๋ฒˆ๊ณผ 5๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒˆ๊ณผ 6๋ฒˆ ์ปดํ“จํ„ฐ๊นŒ์ง€ ์ „ํŒŒ๋˜์–ด 2, 3, 5, 6 ๋„ค ๋Œ€์˜ ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ 4๋ฒˆ๊ณผ 7๋ฒˆ ์ปดํ“จํ„ฐ๋Š” 1๋ฒˆ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์˜ํ–ฅ์„ ๋ฐ›์ง€ ์•Š๋Š”๋‹ค

์–ด๋Š ๋‚  1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ •๋ณด๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, 1๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ํ†ตํ•ด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋˜๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋Š” 100 ์ดํ•˜์ด๊ณ  ๊ฐ ์ปดํ“จํ„ฐ์—๋Š” 1๋ฒˆ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ ์Œ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ ๊ทธ ์ˆ˜๋งŒํผ ํ•œ ์ค„์— ํ•œ ์Œ์”ฉ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ์˜ ๋ฒˆํ˜ธ ์Œ์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ์„ ๋•Œ, 1๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ํ†ตํ•ด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋˜๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋ฅผ ์ฒซ์งธ ์ค„์— ์ถœ๋ ฅํ•œ๋‹ค.

 

๋”๋ณด๊ธฐ

์˜ˆ์ œ ์ž…๋ ฅ

7
6
1 2
2 3
1 5
5 2
5 6
4 7

์ •๋‹ต : 4

 

2. ์ฝ”๋“œ

let count = Int(readLine()!)!	//์ฒซ ๋ฒˆ์งธ ์ค„์€ ์ปดํ“จํ„ฐ์˜ ์ˆ˜ 
let pairs = Int(readLine()!)!	//๋‘˜์งธ ์ค„์€ ์ปดํ“จํ„ฐ ์Œ์˜ ์ˆ˜

var graph : [Int : [Int]] = [:]

for i in 0..<pairs{	// for in ๋ฌธ์„ ์ด์šฉํ•˜์—ฌ ์ž…๋ ฅ๋ฐ›๋Š” pairs ์ˆ˜๋งŒํผ ๋ฐ˜๋ณต์„ ๋Œ๋ ค ๋‹ค๋ฅธ ๊ฐ’๋“ค์„ ๋ฐ›์•„์ฃผ๊ธฐ
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }	// ๊ณต๋ฐฑ ๊ธฐ์ค€ ์ž˜๋ผ ๋ฐฐ์—ด ๋งŒ๋“ค๊ธฐ
    let key = input[0]
    let value = input[1]
    
    // ์–‘ ๋ฐฉํ–ฅ ๋‘˜๋‹ค ๋„ฃ๊ธฐ
    if var temp = graph[key] {
        temp.append(value)
        graph[key] = temp
    } else {
        graph[key] = [value]
    }

    if var temp = graph[value] {
        temp.append(key)
        graph[value] = temp
    } else {
        graph[value] = [key]
    }
    
}

print(bfs(graph: graph))

func bfs(graph: [Int: [Int]]) -> Int{

    // ์ค‘๋ณต ๋ฐฉ์ง€
    var visited = Set<Int>()
    
    var queue = [1]
    visited.insert(1)   // ๋ฏธ๋ฆฌ ๋„ฃ๊ธฐ
    
    while !queue.isEmpty{
        let currentNode = queue.removeFirst()   // ํƒ์ƒ‰ํ•  ๋…ธ๋“œ ๋นผ๊ธฐ ํ ์ฒซ ๋ฒˆ์งธ์—์„œ
        
        if let temp = graph[currentNode] {  // ํ˜„์žฌ ํƒ์ƒ‰ํ•˜๋Š” ๋…ธ๋“œ ์ธ์ ‘ ๋…ธ๋“œ๋“ค ํƒ์ƒ‰
            for node in temp{               // ์ธ์ ‘ ๋…ธ๋“œ๋“ค ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ ์žˆ๋Š”์ง€ ํ™•์ธ
                if visited.contains(node){
                    continue
                }
                visited.insert(node)        // ์—†์œผ๋ฉด ๋ฐฉ๋ฌธํ•˜๊ณ  ํ์— ๋Œ€๊ธฐ ์‹œํ‚ค๊ธฐ
                queue.append(node)
            }
        }

    }

    return visited.count - 1
}

 

3. ์ฝ”๋“œ ์„ค๋ช…

์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๋ฅผ ์ค€๋น„ํ•˜๋ฉด์„œ BFS ๊ด€๋ จ ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ์œผ๋กœ ์ ‘ํ•˜๊ฒŒ ๋œ ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ๐Ÿ˜…
๊ทธ๋ž˜ํ”„ ๊ด€๋ จํ•ด์„œ๋Š” ๋”์šฑ ๊ณต๋ถ€ํ•˜๊ณ  ์ •๋ฆฌ๋ฅผ ํ•œ ๋‹ค์Œ์— ๋ธ”๋กœ๊ทธ์— ๋‹ค๋ฅธ ์นดํ…Œ๊ณ ๋ฆฌ์— ํฌ์ŠคํŒ…ํ•ด์•ผ ํ•  ๊ฑฐ ๊ฐ™์Šต๋‹ˆ๋‹คใ…‹ใ…‹

// 1๋ฒˆ
if var temp = graph[key] {
    temp.append(value)
    graph[key] = temp
} else {
    graph[key] = [value]
}

// 2๋ฒˆ
if var temp = graph[value] {
    temp.append(key)
    graph[value] = temp
} else {
    graph[value] = [key]
}

์ด ๋ถ€๋ถ„์€ ์ œ๊ฐ€ ์ฒ˜์Œ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ์‹ค์ˆ˜ํ•œ ๋ถ€๋ถ„์ž…๋‹ˆ๋‹ค. ์ฒ˜์Œ์—๋Š” 1๋ฒˆ ์ฝ”๋“œ๋งŒ ์ž‘์„ฑํ•˜๊ณ  2๋ฒˆ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ๊ทธ๋ž˜ํ”„์˜ ๋ฐฉํ–ฅ์„ฑ์— ๋Œ€ํ•ด ์ œ๋Œ€๋กœ ๊นจ๋‹ซ์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.
1๋ฒˆ๊ณผ 2๋ฒˆ์„ ๊ฐ„๋‹จํžˆ ํ•ด์„ํ•˜์ž๋ฉด

var graph: [Int: [Int]] = [:]


์œ„ ์ฝ”๋“œ์—์„œ ์ œ๊ฐ€ ๋งŒ๋“  ๊ทธ๋ž˜ํ”„์˜ ๊ตฌ์กฐ๋Š” ๋”•์…”๋„ˆ๋ฆฌ ํ˜•ํƒœ๋กœ ๋˜์–ด ์žˆ์œผ๋ฉฐ, key ๊ฐ’์€ Int ํ˜•์ด๊ณ  / value ๊ฐ’์€ [Int] ๋ฐฐ์—ด๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๋งŒ๋“  ์ด์œ ๋Š” 1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋‹ค๋ฅธ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— [Int]๋ฅผ ๋งŒ๋“ค์–ด 1๋ฒˆ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ๋“ค์˜ ๊ฐ’๋“ค์„ ์ €์žฅํ•˜๋ ค๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

1๋ฒˆ ์ฝ”๋“œ์—์„œ์˜ if var temp = graph[key] ๋ถ€๋ถ„์€ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉด์„œ graph[key] ๊ฐ’์ด ์žˆ๋‹ค๋ฉด ๊ทธ ๊ฐ’์„ ์ž„์‹œ๋กœ temp ๊ฐ’์œผ๋กœ ๊ฐ€์ ธ์™€ ์ƒˆ๋กœ์šด ๊ฐ’์ธ value๋ฅผ appendํ•˜์—ฌ ๋‹ค์‹œ ํ•ด๋‹นํ•˜๋Š” graph[key] ๊ฐ’์— ๋„ฃ์–ด์ฃผ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
๋งŒ์•ฝ graph[key]์ด ์—†๋‹ค๋ฉด ๊ทธ๋Œ€๋กœ graph[key] = [value] ๊ฐ’์„ ๋„ฃ์–ด ๋‹ค์Œ ์ˆœ์„œ๋กœ ๋„˜์–ด๊ฐ‘๋‹ˆ๋‹ค.

์ง€๊ธˆ ์ด ๊ณผ์ •์„ 1๋ฒˆ ์ฝ”๋“œ๋งŒ ์‚ด๋ฆฐ๋‹ค๋ฉด ์ด ๊ทธ๋ž˜ํ”„์˜ ๋ฐฉํ–ฅ์€ ๋‹จ๋ฐฉํ–ฅ์ž…๋‹ˆ๋‹ค.


์—ฌ๊ธฐ์„œ ์ œ ์‹ค์ˆ˜๊ฐ€ ๋‚˜์™”์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ์—์„œ๋Š” ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋ชจ๋“  ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์—

1 -> 2 ๊ด€๊ณ„๋ผ๋ฉด 2 -> 1 ๋„ ๋‹น์—ฐํžˆ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ 1๋ฒˆ๋งŒ ์‚ด๋ฆด ๊ฒฝ์šฐ์—๋Š” ์—ฐ๊ฒฐ์ด ๋Š๊ฒจ ์žˆ์–ด์„œ ์ ˆ๋Œ€์ ???!์œผ๋กœ ์ •๋‹ต์„ ๋งžํžˆ์ง€ ๋ชปํ•ฉ๋‹ˆ๋‹ค.
๊ทธ๋ž˜์„œ 2๋ฒˆ ์ฝ”๋“œ๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ์ด์œ ๋Š” ์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด์„œ์ž…๋‹ˆ๋‹ค. key์™€ value์˜ ๊ฐ’์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟ”์„œ ์ €์žฅํ•ด ์คŒ์œผ๋กœ์จ ์–‘๋ฐฉํ–ฅ ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

์ฃผ์–ด์ง„ ์ฝ”๋“œ์—์„œ๋Š” BFS๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๊ทธ๋ž˜ํ”„๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๊ณผ์ •์„ ๊ตฌํ˜„ํ•˜์˜€์Šต๋‹ˆ๋‹ค.


1. ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ๊ทธ๋ž˜ํ”„๋ฅผ ๊ตฌ์„ฑํ•œ ํ›„, bfs ๋ฉ”์„œ๋“œ์— ๊ทธ๋ž˜ํ”„๋ฅผ ์ „๋‹ฌํ•ฉ๋‹ˆ๋‹ค.


2. ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋“ค์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด visited๋ผ๋Š” Set์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค. ์ด Set์€ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋“ค์˜ ๊ฐ’์„ ์ €์žฅํ•˜์—ฌ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.


3. Queue์ธ queue ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜์—ฌ ์‹œ์ž‘์ ์œผ๋กœ 1์„ ๋„ฃ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ์—์„œ 1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ๋‹ค๊ณ  ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ๋˜ํ•œ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ฅผ ์ฒดํฌํ•˜๊ธฐ ์œ„ํ•ด visited์—๋„ ์ดˆ๊ธฐ์— 1์„ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.


4. while ๋ฌธ์„ ํ†ตํ•ด Queue๊ฐ€ ๋น„์–ด์žˆ์ง€ ์•Š์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ Queue๋Š” FIFO(First-In, First-Out)์˜ ๊ฐœ๋…์„ ํ™œ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, ๋จผ์ € ๋“ค์–ด์˜จ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.


5. ๋ฐ˜๋ณต๋ฌธ ์•ˆ์—์„œ๋Š” Queue์—์„œ ํ˜„์žฌ ๋…ธ๋“œ ๊ฐ’์„ ๊บผ๋‚ด๊ณ , ํ•ด๋‹น ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ๋…ธ๋“œ๋“ค์„ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ์ „๋‹ฌ๋ฐ›์€ ๊ทธ๋ž˜ํ”„์ธ graph์—์„œ ํ˜„์žฌ ๋…ธ๋“œ์˜ ๊ฐ’์„ key๋กœ ๊ฐ€์ง€๋Š” ๋ฐฐ์—ด์„ ๊ฐ€์ ธ์˜ต๋‹ˆ๋‹ค.


6. ๊ฐ€์ ธ์˜จ ๋ฐฐ์—ด์„ for-in ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ์ฐจ๋ก€๋Œ€๋กœ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ํ˜„์žฌ ํ™•์ธํ•˜๋Š” ๋…ธ๋“œ๊ฐ€ ์ด๋ฏธ visited ์— ํฌํ•จ๋˜์–ด ์žˆ๋‹ค๋ฉด ๋‹ค์Œ ์š”์†Œ๋กœ ๋„˜์–ด๊ฐ‘๋‹ˆ๋‹ค. ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ์ด๋ฏ€๋กœ ๋‹ค๋ฅธ ์ž‘์—…์„ ํ•  ํ•„์š”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋Š” ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ queue ์— ๋„ฃ๊ณ , visited ์—๋„ ๊ฐ’์„ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•จ์œผ๋กœ์จ ๊ฐ์—ผ๋œ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋œ ์ปดํ“จํ„ฐ๋“ค์„ ํƒ์ƒ‰ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


7. ์—ฐ๊ฒฐ๋œ ์ปดํ“จํ„ฐ๊ฐ€ ๊ณ„์† ์žˆ๋‹ค๋ฉด while ๋ฌธ์€ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋˜๊ณ , visited์—๋Š” ๊ฐ์—ผ๋œ ์ปดํ“จํ„ฐ๋“ค์˜ ๊ฐ’๋“ค์ด ์ €์žฅ๋ฉ๋‹ˆ๋‹ค.


8. while๋ฌธ์„ ๋ชจ๋‘ ๋Œ๊ณ  ๋‚˜๋ฉด queue ๋ฐฐ์—ด ์•ˆ์— ๊ฐ’์ด ์—†๋‹ค๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” ๋” ์ด์ƒ ๊ฐ์—ผ๋œ ์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋œ ์ปดํ“จํ„ฐ๊ฐ€ ์—†๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๊ฒฐ๊ณผ ๊ฐ’์œผ๋กœ ๋ฐฉ๋ฌธํ•œ visited์˜ ์š”์†Œ ๊ฐœ์ˆ˜์— -1์„ ํ•œ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค. 1๋ฒˆ ์ปดํ“จํ„ฐ๋ถ€ํ„ฐ ์‹œ์ž‘ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— 1์„ ๋บ€ ๊ฐ’์ด ์ •๋‹ต์ด ๋ฉ๋‹ˆ๋‹ค.

 

 


๊ธ€์„ ์“ฐ๋‹ค ๋ณด๋‹ˆ ์ข€ ๋” ์ž์„ธํ•˜๊ฒŒ ์„ค๋ช…ํ•˜๊ณ  ์‹ถ์€ ๋งˆ์Œ์— ๊ธ€์ด ๊ธธ์–ด์กŒ์Šต๋‹ˆ๋‹คใ…Žใ…Ž ๐Ÿ˜ฎ
์ €๋„ ์ฒ˜์Œ์— ํ’€ ๋•Œ๋Š” ์ •๋ง ์ดํ•ด๊ฐ€ ์•ˆ ๊ฐ€๊ณ  ์—ฌ๋Ÿฌ ๋‹ค๋ฅธ ๋ธ”๋กœ๊ทธ๋ฅผ ๋ฐฉ๋ฌธํ•ด ๊ฐ€๋ฉด์„œ ์ œ๊ฐ๊ฐ ๋‹ค๋ฅธ ์ฝ”๋“œ์ง€๋งŒ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๋ฐฉ์‹์— ๋Œ€ํ•ด์„œ ๊ณ„์† ์ƒ๊ฐํ•ด ๋ดค๋˜ ๊ฑฐ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๋ฌผ๋ก  ์ €๋„ ๋‹ค๋ฅธ ์œ ํ˜•์˜ ๋ฌธ์ œ๋ฅผ ํ’€๊ฒŒ ๋œ๋‹ค๋ฉด ์ฒ˜์Œ๋ถ€ํ„ฐ ์ด ์ •๋„๋กœ ํ•ด์„ค์ด ์•ˆ๋  ๊ฑฐ ๊ฐ™์Šต๋‹ˆ๋‹คใ…‹ใ…‹;;

๊ทธ๋ž˜๋„ ํ˜น์‹œ๋‚˜ ์ด ๋ฌธ์ œ์— ๋Œ€ํ•ด์„œ ์ œ๊ฐ€ ์ƒ๊ฐํ•˜๋Š” ๋ถ€๋ถ„์ด ํ•„์š”ํ•œ ๋ถ„์ด ๊ณ„์‹ค ์ˆ˜๋„ ์žˆ์œผ๋‹ˆ ๊ฐ€๋ณ๊ฒŒ ์ฝ์–ด์ฃผ์‹œ๊ณ  ๋‹ค๋ฅธ ๋ฌธ์ œ๋“ค๋„ ํŒŒ์ดํŒ… ํ•˜์‹ญ์‹œ์˜คแ„’แ„’๐Ÿ‘