Softeer Level 3 우물 안 개구리 Python

문제 링크

https://softeer.ai/practice/6289

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
weights = list(map(int, input().split()))
adjL = [[] for _ in range(N+1)]

for _ in range(M):
    start, to = map(int, input().split())
    adjL[start].append(to)
    adjL[to].append(start)

V = [1 for _ in range(N+1)]
for p in range(1, N+1):
    currentPW = weights[p-1]
    for nextP in adjL[p]:
        nextPW = weights[nextP-1]
        if nextPW >= currentPW:
            V[p] = 0
            break
print(sum(V)-1)

풀이 방법

1. adjL을 만들어서 각자 아는 사람 명단을 정리한다.
2. 완전 탐색으로 모든 사람을 판단한다.
   1. 현재 사람이 들 수 있는 무게와 아는 사람 무게를 비교한다.
   2. V 배열에 현재 사람이 최고가 아니면 0을 넣는다.
3. 마지막으로 V배열의 합에 -1(0번 째 사람 없음) 하고 출력한다.

느낀점

- 연관된 모든 사람을 dfs로 깊게 침투해서 찾아야 하는 문제인 줄 착각했다.

- 그냥 단순하게 A가 아는 사람 중에 자기가 최고인지 찾는 문제였다.