[BOJ][17143] 낚시왕

문제 : www.acmicpc.net/problem/17143

---

시뮬을 돌려봅시당.

 

상어의 위치를 key값, 상어 정보(크기, 방향, 속도)를 value로 하는 map을 하나 만든다.

낚시꾼은 열의 왼쪽부터 오른쪽으로 한 칸 씩 정기적으로 이동한다.

따라서 0열부터 R-1까지 이동하면서 탐색중인 열의 0행부터 C-1까지 상어들을 탐색하며 가장 위에 있는 상어 정보를 가져온다.

해당 상어를 낚시왕이 잡게 될 것이고 따라서 이 ㄴ상어의 크기를 정답에 더해준 뒤 상어 map에서 삭제한다.

 

낚시왕이 어떤 상어를 잡게 될지 시뮬해보았기 때문에 이제 상어들을 이동시킨다.

상어의 이동방향대로 이동시키면 되는데 문제는 속도이다. 속도의 최대값은 1000이여서 모든 상어들(RxC = 10000)을 낚시왕이 상어를 잡는 동안(C = 100) 상어를 움직이는데 10000(RxC) x 100(C) x 1000(s) = 10^9. 최악의 경우 10^9 만큼 소요되기 때문에 1억을 넘어서 제한시간 1초만에 풀 수 없다.

 

조건에 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다는 문구가 있다.

즉, 상어가 이동하는데 방향을 2번 바꾸면 원래 방향이 될 테이고 위아래, 좌우로만 이동하기 때문에 이동 중 원래 위치, 원래 방향을 바라보게 될 가능성이 있다.

이를 직접 세어봤을 때, 위아래인 경우 (행의 크기(R) - 1)을 2번 반복하는 경우 원래 상태로 돌아왔고, 좌우인 경우 열의 크기(C) - 1)을 2번 반복하는 경우 원래 상태로 돌아왔다.

따라서 속도 횟수 만큼 상어를 이동시킨 것과 속도 % ( 2 * (R-1 or C-1)) 번 상어를 이동 시킨 것이 같다. 모듈러 연산으로 상어의 이동 횟수를 감소시켰다.

조건에 맞게 상어를 이동 시킨 후 원래 상어의 위치, 정보를 저장하던 map과 별개의 map을 만들어서 이동한 뒤의 상어 정보는 새로 만든 map에 저장한다. 만약 이미 map에 있는데 같은 좌표 상에 상어 정보를 저장하려고 할 때, 상어 크기를 비교한 뒤 정보를 갱신할지 판단한다.

모든 상어를 이동 시킨 뒤에는 원래 상어 map에 새로 만든 상어 map 정보로 덮어쓴다.

 

시간복잡도는 R, C를 N으로 했을 때, 낚시꾼이 열을 한 번 방문하므로 O(N). 방문시 잡을 수 있는 상어를 알기 위해 행을 방문하는데 O(N). 상어를 이동시키는데 O(M) 번 탐색하는데, 탐색 시 최대 N 모듈러 연산을 하게 되므로 O(N)이 소요된다. 

이를 종합하면 대충 O(N * (N + NM)) = O(N^2 * M) 이 된다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/17143.%20%EB%82%9A%EC%8B%9C%EC%99%95.cpp