[Swift 백준] 5567 결혼식

풀이 아이디어

그래프 탐색 문제입니다.

문제를 조금 자세히 읽어봐야하는데

초대 인원은 자신의 친구, 친구의 친구까지입니다.

본인과의 거리가 2까지인 사람이 초대받는 사람입니다.

 

방문배열과 거리배열을 사용해서 bfs로 풀이했습니다.

 

 

풀이

 

let n = Int(readLine()!)!
let m = Int(readLine()!)!

var graph: [[Int]] = Array(repeating: [], count: n + 1)

for _ in 0..<m {
    let ab = readLine()!.split(separator:" ").map{Int($0)!}
    let (a,b) = (ab[0],ab[1])
    //양방향 그래프입니다
    graph[a].append(b)
    graph[b].append(a)
}

var isVisited: [Bool] = Array(repeating: false, count: n + 1)
var distance: [Int] = Array(repeating: -1, count: n + 1)

func bfs() {
// 따로 인자는 받지않고 주인공을 시작점으로 함수를 만들었습니다
    var q = [1]
    isVisited[1] = true
    distance[1] = 0
    
    while !q.isEmpty {
        let current = q.removeFirst()
        
        for next in graph[current] {
            if !isVisited[next] {
            //방문처리와 거리를 증가시켜줍니다.
                isVisited[next] = true
                distance[next] = distance[current] + 1
                q.append(next)
            }
        }
    }
    
    var count = 0
    //본인을 제외한 모든 사람의 거리를 가져옵니다
    for i in 2..<n+1 {
        if distance[1] == 1 || distance[i] == 2 {
            count += 1
        }
    }
    
    print(count)
}

bfs()