알고리즘 문제풀이/백준

[Seop's의 코드풀이] 백준 5567 결혼식 - Python

섭섭군 2020. 6. 3. 18:14
반응형

이번에 풀어볼 문제는 백준 5567번 결혼식 문제입니다.

문제는 다음과 같습니다.

 

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

 

5567번: 결혼식

문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

www.acmicpc.net

 

처음에 접근할 때에는 트리를 이용해서 풀어볼까 생각했지만 다른 간단한 방법도 생각나서 풀이를 진행했습니다.

 

접근 아이디어

- 1번(나)를 포함하여 모든 동기의 번호를 dict에 저장한다.

- 1번(나)이 가지고 있는 Value를 Set(집합, 중복을 허용하지 않는다.)로 저장시킨다.

- 1번(나)이 가지고 있는 각각의 값들의 Value를 집합에 Update 한다.

- 집합의 길이에서 -1 ( 1번도 포함되어 있으므로 제거한다)를 출력한다.

 

위 아이디어에서 진행한 dict 는 다음과 같은 형식을 따릅니다.

Key : 학번

Value : 친구들의 학번들

 

전체적인 코드는 다음과 같습니다.

질문과 피드백은 언제나 감사드립니다.

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    m = int(input())
    friend = dict()

    for i in range(1, N+1) :
        friend[i] = []
    
    for _ in range(m) :
        a, b = map(int, input().split(" "))
        friend[a].append(b)
        friend[b].append(a)
    
    ans_set = set(friend[1])
    for i in friend[1] :
        ans_set.update(friend[i])
    print(len(ans_set) - 1)
반응형