[백준] 1058번 친구 파이썬 해설 (Python)

출처 : https://www.acmicpc.net/problem/1058

1058번: 친구

그래프 이론 알고리즘으로 분류된 문제이다.

문제를 다 풀고 다른 사람들의 풀이를 참고하며 공부했는데 플로이드 와샬 알고리즘을 사용했었다.

기존에 있던 알고리즘을 사용하지 않고 나만의 알고리즘을 설계하여 풀었는데,

플로이드 와샬 알고리즘을 사용할 때보다 좋은 성적이 나와서 뿌듯했던 문제이다.

 

풀이

---

문제를 풀기 위한 나의 의식의 흐름을 나열해보겠다.

1. 필요한 데이터 정리 - 친구 목록 그래프, 친구가 아닌 사람들에 대한 그래프, 2-친구에 대한 그래프
2. 문제에서 제공하는 입력 데이터를 친구 목록 그래프와 친구가 아닌 사람들에 대한 그래프에 분배
3. 친구가 아닌 사람들에 대한 그래프 중 2-친구 관계에 있는지 확인
4. 2-친구 조건에 합당하면 2-친구에 대한 그래프에 추가

플로이드 와샬 알고리즘으로 풀 수 있다는 생각을 하지도 못했는데, 내가 직접 구현한 위의 알고리즘으로 2등을 했다.

기분이 상당히 좋았다.

 

아래는 정답에 사용한 코드이다.

import sys
input=sys.stdin.readline

if __name__ == "__main__":
    num = int(input())
    fnd = [[] for i in range(num)]
    no_fnd = [[] for i in range(num)]
    fnd_second = [[] for i in range(num)]
    for i in range(num):
        for idx, v in enumerate(input()):
            if v == 'Y' :
                fnd[i].append(idx)
            elif v == 'N' and i != idx:
                no_fnd[i].append(idx)
    for idx, v in enumerate(no_fnd):
        for name in v:
            if len(set(fnd[name]) - set(fnd[idx])) != len(fnd[name]):
                fnd_second[idx].append(name)
    m = 0
    for i in range(num):
        if m < len(fnd[i] + fnd_second[i]):
            m = len(fnd[i] + fnd_second[i])
    print(m)

 

결과 인증

---

1등과 큰 차이가 나지 않아서 아쉽긴 했지만, 전형적인 풀이 방법보다 좋은 성적을 받았다는 점에서 프로그래밍 공부에 대한 보람을 느낄 수 있는 문제였다.

한 번의 시도로 2등을 해서 더 보람을 느낄 수 있던 문제였다!