5567번: 결혼식

문제 풀이 아이디어

# 자료구조/알고리즘
    : bfs
# 풀이방법
    1. 입력받은 친구관계를 인접리스트로 만듭니다.
    2. bfs를 통해서 거리가 2 이내의 친구만 셉니다.

코드

// 큐 구현
struct Queue {
    var queue = [(Int, Int)]()
    var index = 0
    
    var isEmpty: Bool {
        queue.count - index == 0
    }
    
    mutating func push(_ tuple: (Int, Int)) {
        queue.append(tuple)
    }
    
    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return queue[index]
    }
}

// bfs 구현
func bfs() {
    var queue = Queue()
    var check = Array(repeating: false, count: n + 1)
    var cnt = 0 //👉 참석자를 세기 위한 변수
    queue.push((1, 0)) //👉 학번 + 1번과의 거리를 튜플로 묶어서 push
    check[1] = true
    
    while !queue.isEmpty {
        let now = queue.pop()
        //🚫 (친구의 친구)의 친구는 추가하지 않는다. (길이 2 = 친구의 친구)
        if now.1 > 1 {
            break
        }
        
        // 인접리스트를 돌면서 친구를 추가한다.
        for i in adj[now.0] {
            if check[i] { continue }
            queue.push((i, now.1 + 1))
            check[i] = true
            cnt += 1
        }
    }
    
    print(cnt)
}

// 입력 받기
let n = Int(readLine()!)!
let m = Int(readLine()!)!

// 인접리스트
var adj = Array(repeating: [Int](), count: n + 1)

// 양방향 그래프이므로 인접 리스트의 양방향에 모두 추가
for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    adj[input[0]].append(input[1])
    adj[input[1]].append(input[0])
}

bfs()