[Python] 백준(BOJ) - 5567 결혼식

필자는 거의 항상 코딩 테스트, 혹은 알고리즘 문제 풀이를 파이썬으로 한다.

대체로 코딩 테스트는 C++로 하라고 하지만... 필자가 일하고자 하는 직무가 인공지능, 빅데이터 쪽이기도 하고,

C, C++은 임베디드 하면서도 자주 접하기 때문에 지식의 반경을 넓히고자 하는 욕심도 있기 때문이다.

 

이번 알고리즘 풀이 첫 문제는, 백준 온라인 저지의 5567번 문제 결혼식이다.

정답률도 41% 정도의 쉬운 문제지만,

이 문제를 처음으로 올리는 이유는, 필자가 처음으로(부끄럽다...) 랭크에 올라봤기 때문이다.

 

한 번 바로 살펴보자.

---

소스 코드

#BOJ 5567 결혼식 (Graph)

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
res = dict()
resSet = set()

for _ in range(m):
    key, item = map(int, input().split())
    if key not in res:
        res[key] = list()
    if item not in res:
        res[item] = list()
    res[key].append(item)
    res[item].append(key)
    
for key in res[1]:
    resSet.add(key)
    if key not in res:
        continue
    else:
        for item in res[key]:
            resSet.add(item)

print(len(resSet) - 1)

원래 이 문제는 양방향 그래프를 구현해보는 목적의 문제이다.

하지만 막상 이 문제를 양방향 그래프로 구현하자니 너무 쉽고 빠른 길(dictionary 자료형과 set 자료형 활용)이 보이기에 무시할 수가 없었다.

 

아무래도 dictionary 자료형과 set 자료형의 활용이 시간복잡도 면에서 조금이라도 더 우세할 것 같아서 그렇게 했더니, 그 결과는,

역시 맞았다. 한 번에 맞추진 못했지만.

역시 파이썬의 dictionary 자료형과 set 자료형은 너무 강력하다.

몇 줄 안되는 코드로 바로 맞췄다.

(시도 자체는 5번 했으나 사소한 오타 때문이었다.)

 

그리고...

언어 Column의 Python 3 / 수정 이 보이는가?

4등에 들었다.

 

참고로 1 ~ 5등이 68ms, 6 ~ 10등이 72ms, 11등이 76ms, 그 이후로는 80ms 이상이다.

(그래도 35등까지는 146ms이다가, 그 이후부터는 갑자기 436ms로 훅 뛴다. 무슨 알고리즘인지는 모르겠다.)

 

백준에는 하도 괴물 같은 고수분들이 많아서, 랭크와는 담을 쌓고 살았는데,

양방향 그래프 대신 dictionary와 set를 쓴 게 컸다.

 

역시 프로그래밍은 공부할수록 재미있다.

이러한 소소한 재미, 특히 쓰라는 대로 쓰기보다는 더 재밌을 것 같고 더 좋을 것 같은 방법을 적용시켜 더 나은 결과물을 획득하는 소소한 재미가 너무 매력적이라 생각한다.