[BOJ] 1325번: 효율적인 해킹

https://www.acmicpc.net/problem/1325


기본적으로 모든 컴퓨터에 대해 flood fill로 연속적으로 해킹할 수 있는 가지수를 계산하면 됩니다. SCC로 시간을 조금 줄일수는 있다만 그래도 시간복잡도는 여전히 O(NM)입니다. N*M이 최대 10^9 이기 때문에 조금 간당간당하긴 하지만 시간제한이 5초로 넉넉한 편이라  SCC를 쓰지 않더라도 시간 내에 통과가 가능합니다.


https://github.com/encrypted-def/BOJ/blob/master/1325.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1766번: 문제집  (0) 2018.01.09
[BOJ] 1516번: 게임 개발  (0) 2018.01.09
[BOJ] 3665번: Rankings  (0) 2018.01.09
[BOJ] 10216번: Count Circle Groups  (0) 2018.01.07
[BOJ] 1289번: 트리의 가중치  (0) 2018.01.07
[BOJ] 1693번: 트리 색칠하기  (2) 2018.01.07
  Comments