사용자 도구

사이트 도구


ps:problems:boj:25195

Yes or yes

ps
링크acmicpc.net/…
출처BOJ
문제 번호25195
문제명Yes or yes
레벨골드 4
분류

그래프순회

시간복잡도O(V+E)
인풋사이즈V<=100,000, E<=100,000
사용한 언어Python
제출기록54992KB / 252ms
최고기록236ms
해결날짜2022/11/18
출처

제1회 곰곰컵

풀이

  • 팬클럽 곰곰이가 있는 노드를 지나지 않고, 싱크 노드까지 가는 경로가 존재하는지 여부를 확인하면 된다.
  • 그냥 팬클럽 곰곰이가 있는 노드를 '벽'으로 지정하고 BFS나 DFS를 돌리면 된다 (2D 그리드에서 미로찾기를 하는 문제들 처럼..). 도달 가능한 노드들 중에서 싱크노드가 있으면 'yes'를 출력하고 아니면 'Yes'를 출력하면 끝.
  • 시간복잡도는 O(V+E)
  • 언제 'Yes'를 출력하고 언제 'yes'를 출력해야 하는지 헷갈리지 않도록 주의.. 출발지점에 팬클럽이 있는 경우도 있을수 있으니 그런 경우도 주의.

코드

"""Solution code for "BOJ 25195. Yes or yes".

- Problem link: https://www.acmicpc.net/problem/25195
- Solution link: http://www.teferi.net/ps/problems/boj/25195

Tags: [graph traversal]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')
SOURCE = 0


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        graph[u - 1].append(v - 1)
    S = int(sys.stdin.readline())  # pylint: disable=unused-variable
    s = [int(x) for x in sys.stdin.readline().split()]

    dists = [INF] * N
    for u in s:
        dists[u - 1] = -1
    for u in tgraph.bfs_iter(graph, SOURCE, distances=dists):
        if not graph[u]:
            print('yes')
            break
    else:
        print('Yes')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
A M O M J
 
ps/problems/boj/25195.txt · 마지막으로 수정됨: 2022/11/26 03:42 저자 teferi