[BOJ] 백준 17143. 낚시왕

▶문제설명

[BOJ] 백준 17143. 낚시왕

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

▶Hint

---

[삼성전자 상시 SW역량테스트-A형] 시뮬레이션 문제이다.

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

2. 상어를 낚음

3. 상어들이 움직임

1~3 과정을 C번(문제에서 주어진 열의 크기만큼) 수행하면 답을 구하게 되는 문제이다.

상어 구조체를 만들고 상어들의 상태와 위치를 2차원 배열로 관리했다.

3번에서 상어들이 움직일 때 예를 들어, 상어의 속력이 5인 경우 5번에 걸쳐 이동시키면서 매번 상어가 범위를 벗어났는지 파악하여 상태를 변경하는 방법으로 구현했다.

문제 해결에 있어 핵심이 되는 부분에 대해 설명하고자 한다.

[구조체 선언]

struct Shark {
    int s, d, z;
}map[101][101], tmp[101][101];
 

상어를 이동시키는 과정에서 오류가 없으려면 현재 상태를 저장해두고 그것을 이용해 다음 상태를 만들어주어야 한다.

그러지 않으면 현재 상어가 있는 (x,y)로 상어가 이동한 뒤, 원래 (x,y)에 있던 상어가 이동할 경우 처리하기가 곤란해지기 때문이다.

[시간복잡도 개선]

Shark sk = map[i][j];
 
if (sk.d == 1 || sk.d == 2)
    sk.s %= ((R-1)*2);
else
    sk.s %= ((C-1)*2);

모듈러 연산을 통해 불필요한 연산을 줄이는 부분이다.

상어가 움직이는 방향이 위/아래인 경우 (R-1)*2번, 좌/우인 경우 (C-1)*2번 이동하면 원 상태로 돌아오기 때문에

해당 값으로 모듈러 연산을 해주면 딱 필요한 만큼만 연산하게 된다.

이 부분을 생략하면 실행 시간이 초과된다.

[상어가 범위를 벗어난 경우]

if (R < nextR)       nextR -= 2;
else if (nextR < 1)  nextR += 2;
else if (C < nextC)  nextC -= 2;
else if (nextC < 1)  nextC += 2;
 
sk.d = conv[sk.d];
r = nextR;
c = nextC;

C 열에 위치한 상어가 오른쪽으로 한 칸 이동해서 C+1열에 위치하게 되어 범위를 초과한 경우를 생각해보자.

원래 상어가 위치해야 할 곳은 C-1열이므로 -2를 해주어야 하고 상어가 이동하는 방향도 반대로 바꾸어 주어야 한다.

▶Solution

---

[소스코드 보기]