Today
38
Total
237,978
Notice
«   2022/07   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
Archives
관리 메뉴

Joonas' Note

BOJ 1613 - 역사 본문

알고리즘/문제 풀이

BOJ 1613 - 역사

joonas 2019. 2. 24. 01:14

    링크: https://www.acmicpc.net/problem/1613

    이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html

    문제

    알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다.


    방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다.


    a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1

    b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다.


    문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. 

    n이 400으로 작으므로 플로이드 와샬로 각 사건의 연결 관계를 모두 구해둔다면, 쿼리의 대답이 O(1)이므로 시간 내에 해결 가능하다.

    코드


    반응형

    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 11447 - Colby’s Costly Collectibles  (0) 2019.03.11
    BOJ 1976 - 여행 가자  (0) 2019.03.08
    BOJ 1613 - 역사  (0) 2019.02.24
    BOJ 9465 - 스티커  (0) 2019.02.24
    BOJ 10472 - 십자뒤집기  (0) 2019.02.23
    BOJ 1939 - 중량 제한  (0) 2019.02.23
    0 Comments
    댓글쓰기 폼