이번에는 백준 17143번 낚시왕 문제를 풀어보았습니다.
이 문제는 낚시왕의 이동, 상어 포획, 상어 이동, 같은 칸에 도착한 상어끼리의 크기 비교까지 순서대로 처리해야 하는 시뮬레이션 문제입니다.
특히 상어들은 동시에 이동해야 하기 때문에 현재 상어 위치를 저장하는 배열과 이동 이후의 위치를 저장하는 배열을 분리하여 구현하였습니다.
문제 설명
R × C 크기의 격자판에 여러 마리의 상어가 있습니다.
각 상어는 다음 정보를 가지고 있습니다.
- 위치
- 속력
- 방향
- 크기
낚시왕은 왼쪽에서 오른쪽으로 한 열씩 이동합니다.
각 열에서 다음 순서로 진행됩니다.
- 해당 열에서 가장 위에 있는 상어를 잡습니다.
- 살아있는 모든 상어가 이동합니다.
- 이동이 끝난 뒤 같은 칸에 여러 상어가 있다면 가장 큰 상어만 살아남습니다.
이 과정을 모든 열에 대해 진행한 뒤 낚시왕이 잡은 상어 크기의 합을 구하는 문제입니다.
풀이 아이디어
상어의 정보는 구조체 배열에 저장하였습니다.
struct Shark {
int y, x, s, dir, z, death;
}a[100*100];각 상어마다 현재 위치와 속력, 방향, 크기, 죽었는지를 저장합니다.
현재 격자판에는 상어의 번호를 저장하였습니다.
shark[y][x] = 상어 번호상어 이동이 동시에 이루어져야 하므로 이동 결과는 바로 shark 배열에 저장하지 않고 별도의 temp 배열에 저장하였습니다.
모든 상어 이동이 끝난 뒤
memcpy(shark, temp, sizeof(temp));를 통해 다음 상태로 변경하였습니다.
또한 상어는 같은 구간을 왕복하면서 이동하므로 속력은 전체 왕복 길이로 나눈 나머지만 사용하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
struct Shark {
int y, x, s, dir, z, death;
}a[100*100];
const int dx[] = {0, 0, 1, -1 };
const int dy[] = {-1, 1, 0, 0 };
int shark[max_n][max_n], R, C, M, ret, temp[max_n][max_n];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> R >> C >> M;
for (int i = 1; i <= M; i++) {
cin >> a[i].y >> a[i].x >> a[i].s >> a[i].dir >> a[i].z;
a[i].y--; a[i].x--; a[i].dir--;
if(a[i].dir <= 1) a[i].s %= (2 * (R - 1));
else a[i].s %= (2 * (C - 1));
shark[a[i].y][a[i].x] = i;
}
for (int t = 0; t < C; t++) {
for (int y = 0; y < R; y++) {
if (shark[y][t]) {
a[shark[y][t]].death = 1;
ret += a[shark[y][t]].z;
shark[y][t] = 0;
break;
}
}
memset(temp, 0, sizeof(temp));
for (int i = 1; i <= M; i++) {
if (a[i].death) continue;
int y = a[i].y;
int x = a[i].x;
int s = a[i].s;
int d = a[i].dir;
int ny, nx;
while (1) {
ny = y + s * dy[d];
nx = x + s * dx[d];
if (nx < C && ny < R && ny >= 0 && nx >= 0)break;
if(d <= 1){
if(ny < 0){
s -= y;
y = 0;
}else{
s -= R - 1 - y;
y = R - 1;
}
}else{
if(nx < 0){
s -= x;
x = 0;
}else {
s -= C - 1 - x;
x = C - 1;
}
}
d ^= 1;
}
if (temp[ny][nx]) {
if (a[temp[ny][nx]].z < a[i].z) {
a[temp[ny][nx]].death = 1;
temp[ny][nx] = i;
}else a[i].death = 1;
}else temp[ny][nx] = i;
a[i].y = ny;
a[i].x = nx;
a[i].dir = d;
}
memcpy(shark, temp, sizeof(temp));
}
cout << ret << "\n";
return 0;
}풀이 흐름
-
상어의 위치, 속력, 방향, 크기를 입력받습니다.
-
상어의 방향을 코드에서 사용할 수 있도록 0부터 시작하도록 변경합니다.
-
상어의 속력을 이동 주기로 나눈 나머지로 줄입니다.
-
낚시왕이 0번 열부터 마지막 열까지 한 칸씩 이동합니다.
-
현재 열에서 가장 위에 있는 상어를 잡습니다.
-
죽지 않은 모든 상어를 이동시킵니다.
-
상어의 이동 결과는
temp배열에 저장합니다. -
같은 위치에 여러 상어가 도착하면 가장 큰 상어만 남깁니다.
-
모든 상어 이동이 끝나면
temp를 현재 격자판으로 변경합니다. -
마지막 열까지 진행한 뒤 잡은 상어 크기의 합을 출력합니다.
구현 포인트
1. 상어 정보 구조체
struct Shark {
int y, x, s, dir, z, death;
}a[100*100];각 상어마다 다음 정보를 관리하였습니다.
y, x : 현재 위치
s : 속력
dir : 현재 방향
z : 크기
death: 죽었는지 여부상어가 낚시왕에게 잡히거나 다른 상어에게 잡아먹히면 death를 1로 변경합니다.
이후 이동할 때는 죽은 상어를 제외합니다.
if (a[i].death) continue;2. 방향 배열
const int dx[] = {0, 0, 1, -1 };
const int dy[] = {-1, 1, 0, 0 };문제에서는 방향이 다음과 같이 주어집니다.
1 : 위
2 : 아래
3 : 오른쪽
4 : 왼쪽입력받은 방향에서 1을 빼서 다음과 같이 사용하였습니다.
0 : 위
1 : 아래
2 : 오른쪽
3 : 왼쪽a[i].dir--;따라서 dy, dx 배열의 인덱스와 바로 연결할 수 있습니다.
3. 현재 맵에는 상어 번호 저장
shark[a[i].y][a[i].x] = i;격자판에는 상어 자체의 정보를 저장하지 않고 상어 번호를 저장하였습니다.
따라서 현재 위치에 상어가 있다면 해당 번호를 이용하여 구조체 배열에서 상어의 정보를 가져올 수 있습니다.
예를 들어
a[shark[y][t]]를 통해 해당 위치의 상어 정보를 확인할 수 있습니다.
4. 낚시왕이 가장 가까운 상어 잡기
for (int y = 0; y < R; y++) {
if (shark[y][t]) {현재 낚시왕의 열 t에서 위쪽부터 아래쪽으로 순회합니다.
처음 발견한 상어가 땅에서 가장 가까운 상어이므로 해당 상어만 잡습니다.
a[shark[y][t]].death = 1;
ret += a[shark[y][t]].z;
shark[y][t] = 0;
break;상어를 죽은 상태로 변경하고 크기를 정답에 더한 뒤, 해당 칸을 비웁니다.
한 열에서는 상어 한 마리만 잡을 수 있으므로 바로 break합니다.
5. 상어 이동을 별도 배열에 저장
memset(temp, 0, sizeof(temp));상어는 모두 동시에 이동해야 합니다.
따라서 현재 shark 배열을 직접 수정하면서 이동시키면 먼저 이동한 상어가 아직 이동하지 않은 상어에게 영향을 줄 수 있습니다.
이를 방지하기 위해 이동 결과를 별도의 배열인
temp에 저장하였습니다.
모든 상어가 이동한 뒤에만
memcpy(shark, temp, sizeof(temp));를 수행합니다.
이렇게 하면 모든 상어가 동시에 이동한 것처럼 처리할 수 있습니다.
6. 속력 줄이기
상어는 같은 행 또는 열을 계속 왕복합니다.
세로 방향의 경우 원래 위치로 돌아오는 이동 주기는 다음과 같습니다.
2 × (R - 1)가로 방향에서는
2 × (C - 1)입니다.
따라서 입력받은 속력이 매우 크더라도 다음과 같이 줄일 수 있습니다.
if(a[i].dir <= 1)
a[i].s %= (2 * (R - 1));
else
a[i].s %= (2 * (C - 1));예를 들어 세로 길이가 5라면 이동 주기는
2 × (5 - 1) = 8입니다.
속력이 11이라면 8칸 이동한 뒤 원래 위치와 방향으로 돌아오기 때문에 실제로는 3칸만 이동하면 됩니다.
7. 상어의 이동
현재 상어의 정보를 지역 변수에 저장합니다.
int y = a[i].y;
int x = a[i].x;
int s = a[i].s;
int d = a[i].dir;현재 방향으로 남아 있는 거리 s만큼 한 번에 이동했을 때의 위치를 계산합니다.
ny = y + s * dy[d];
nx = x + s * dx[d];해당 위치가 격자 안이라면 이동이 끝난 것입니다.
if (nx < C && ny < R && ny >= 0 && nx >= 0)
break;범위를 벗어났다면 벽까지 이동한 뒤 남은 거리를 줄이고 방향을 반대로 변경합니다.
8. 세로 방향에서 벽에 도달한 경우
if(d <= 1)방향이 0 또는 1이면 위아래 이동입니다.
위쪽으로 이동하다 범위를 벗어난 경우
if(ny < 0){
s -= y;
y = 0;
}현재 위치에서 위쪽 벽까지 이동한 거리 y만큼을 s에서 빼고 위치를 0으로 변경합니다.
반대로 아래쪽으로 범위를 벗어난 경우에는
s -= R - 1 - y;
y = R - 1;현재 위치에서 아래쪽 벽까지 이동한 거리만큼 빼줍니다.
9. 가로 방향에서 벽에 도달한 경우
else {
if(nx < 0){
s -= x;
x = 0;
}else {
s -= C - 1 - x;
x = C - 1;
}
}왼쪽 또는 오른쪽 벽까지 이동한 만큼 남은 거리에서 빼고, 현재 위치를 벽의 위치로 변경합니다.
이후 남은 거리만큼 반대 방향으로 계속 이동합니다.
10. 방향 반전
d ^= 1;방향을 반대로 바꿀 때 XOR 연산을 사용하였습니다.
현재 방향 번호가 다음과 같이 구성되어 있기 때문입니다.
0 : 위
1 : 아래
2 : 오른쪽
3 : 왼쪽따라서
0 ^ 1 = 1
1 ^ 1 = 0
2 ^ 1 = 3
3 ^ 1 = 2가 되어 서로 반대 방향으로 변경됩니다.
11. 이동 완료 후 같은 칸에 상어가 없는 경우
if (!temp[ny][nx])
temp[ny][nx] = i;이동한 위치에 아직 다른 상어가 없다면 현재 상어 번호를 그대로 저장합니다.
12. 같은 칸에 여러 상어가 도착한 경우
if (temp[ny][nx]) {이미 다른 상어가 이동해온 위치라면 두 상어의 크기를 비교합니다.
기존 상어보다 현재 상어가 크다면
if (a[temp[ny][nx]].z < a[i].z) {
a[temp[ny][nx]].death = 1;
temp[ny][nx] = i;
}기존 상어를 죽이고 현재 상어를 해당 칸에 저장합니다.
반대로 기존 상어가 더 크다면
else
a[i].death = 1;현재 상어가 잡아먹힙니다.
문제에서 같은 크기의 상어는 없다고 했기 때문에 크기가 같은 경우는 고려하지 않아도 됩니다.
13. 상어 위치와 방향 갱신
이동이 끝난 뒤 현재 상어의 상태를 갱신합니다.
a[i].y = ny;
a[i].x = nx;
a[i].dir = d;상어가 이동하면서 벽에 부딪힌 경우 방향이 변경되었을 수 있기 때문에 위치뿐 아니라 방향도 함께 저장해야 합니다.
14. 한 턴의 처리 순서
문제에서 한 초 동안의 순서는 다음과 같습니다.
낚시왕 이동
→ 상어 잡기
→ 상어 이동
→ 같은 위치의 상어끼리 크기 비교코드에서는 낚시왕의 위치를 반복문 변수 t로 관리하였습니다.
for (int t = 0; t < C; t++)따라서 각 반복마다 현재 열에서 상어를 잡고, 이후 모든 상어를 이동시키는 방식으로 문제의 순서를 그대로 구현하였습니다.
15. 시뮬레이션에서 현재 상태와 다음 상태 분리
이 문제에서 가장 중요한 부분은 상어를 한 마리씩 순서대로 이동시키더라도 실제 문제에서는 모두 동시에 이동한다는 점입니다.
따라서
shark : 현재 상태
temp : 이동 완료 후 다음 상태로 분리하였습니다.
현재 상어 위치를 읽을 때는 shark를 사용하고,
이동 완료 위치를 기록할 때는 temp를 사용합니다.
모든 상어의 이동이 끝난 뒤에만
memcpy(shark, temp, sizeof(temp));를 수행합니다.
이 방식으로 동시에 발생하는 상태 변화를 구현할 수 있습니다.
16. 시간복잡도
낚시왕은 총 C개의 열을 이동합니다.
각 열마다 최대 M마리의 상어를 이동시킵니다.
속력은 미리 왕복 주기로 나누어 줄였기 때문에 상어 한 마리의 이동 횟수도 제한됩니다.
따라서 전체적으로는 대략
O(C × M × max(R, C))정도로 볼 수 있습니다.
R, C는 최대 100이고 상어의 수도 최대 R × C이므로 제한 안에서 해결할 수 있습니다.
