백준 17143 낚시왕 C++

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

17143번: 낚시왕

상어를 낚는 낚시왕은 다음과 같이 진행됩니다.

 

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

2. 낚시왕이 있는 열에서 가장 가까운 상어를 잡는다.

3. 상어가 이동한다.

 

핵심은 상어가 이동함을 구현하는 것입니다. 특별한 알고리즘은 없지만, 최대 100 * 100 칸에 상어가 있을 수 있기 때문에 연산을 최소화하여야 합니다.

 

상어의 이동은 다음과 같습니다.

 

1. 상어는 마주보는 방향으로 속력만큼의 칸을 이동합니다.

2. 벽인 경우, 방향을 바꾸어 진행합니다.

3. 상어가 모두 이동하였을 때 같은 칸에 여러 상어가 있는 경우, 크기가 가장 큰 상어만 살아남습니다.

 

처음에 몇 번 틀렸었는데, 속력을 그냥 단순히 1칸씩 이동시켜서 시간초과가 떴습니다.

 

상어의 이동은 방향과 속력에 따라 1번에 계산해주도록 만들면 됩니다. (코드 참고)

왕복 진행 거리 (2 *(R-1) 또는  2 * (C-1)) 을 이용하여 벽을 마주하여 방향을 바꾸는 횟수와 최종 이동 칸을 구해주면 됩니다.

 

코드는 다음과 같습니다.