- Today
- 38
- Total
- 237,978
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 2022/06 (8)
- 2022/05 (5)
- 2022/04 (11)
- 2022/03 (11)
- 2022/02 (1)
- 2022/01 (2)
- 2021/11 (2)
- 2021/10 (2)
- 2021/09 (4)
- 2021/02 (1)
- 2020/07 (1)
- 2020/06 (6)
- 2020/05 (5)
- 2020/04 (5)
- 2020/03 (5)
- 2020/02 (6)
- 2020/01 (6)
- 2019/12 (7)
- 2019/11 (8)
- 2019/09 (7)
- 2019/06 (2)
- 2019/05 (6)
- 2019/04 (4)
- 2019/03 (8)
- 2019/02 (5)
- 2019/01 (2)
- 2018/11 (7)
- 2018/10 (10)
- 2018/09 (2)
- 2018/07 (2)
Joonas' Note
BOJ 1613 - 역사 본문
링크: 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