백준 33706 - 오름차순 최단 경로 (Python)

문제 정보

• https://www.acmicpc.net/problem/33706
• 그리디

---

문제 정리

정점 N개, 간선 M개로 이루어진 무방향 그래프가 주어진다. 간선의 비용을 양의 정수중에 마음대로 정할 수 있을 때, i < j인 정점에 대해 1 -> i 비용이 1 -> j 비용보다 작아야 한다. 이 조건을 만족시키도록 비용을 정할 수 있는지 체크하는 문제이다.

---

풀이

예제 2의 2번 정점은 조건을 만족하지 못한다. 잘 생각해 보면 자신보다 작은 번호의 정점과의 간선이 있다면 조건을 만족할 수 있다. 생각보다 관찰이 어렵다.

뭔가 뭔가임...

---

코드

# 백준 33706

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(N, M, edge):
    isConnect = [False for _ in range(N+1)]
    for _, e in edge:
        isConnect[e] = True

    for i in range(2, N+1):
        if isConnect[i] == False:
            return 'NO'
    return 'YES'


def main():
    N, M = map(int, input().split())
    edge = []
    for _ in range(M):
        edge.append(list(map(int, input().split())))
    print(solve(N, M, edge))


main()