BFS (1) 썸네일형 리스트형 백준 3197 백조의 호수 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 1. 시간 복잡도 시간복잡도를 알면 문제 접근법이 그나마 보인다. 주어지는 R과 C가 각각 1500 이하 이므로 약 10^3이다. O(N^2) 까지는 너끈하지만 O(N^3)은 10^9가 된다. 대강 10억이다... 이건 시간 제한 1초에 무조건 걸리므로 최대 O(N^2 * logN)인 알고리즘을 찾는다. (적어도 N^3은 안된다...) 2. 문제풀이 L이 백조이고 이 둘이 만나는 데 걸리는 날을 .. 이전 1 다음