BOJ 17143 낚시왕

lovinix -

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

아마 코테시즌이 되면 백준에 질문이 가장 많이 올라오는 문제가 아닐까싶은 문제, 낚시왕이다.
개인적으로 기출로 나왔던 시뮬레이션 문제들이 대부분 디스크립션을 한 번에 알아보기 힘들어서 늘 몇 번씩 읽어봤었는데 이 문제는 바로 로직을 구성할 수 있을 정도여서 코드를 짜는데 그렇게 오래걸리지는 않았다.

이런 시뮬레이션 문제에서 시간을 줄이는 가장 확실한 방법은 디버깅시간을 0으로 만드는 것인데, 그렇게 하려면 코드를 짜기 전 문제를 제대로 읽고 로직을 확실히 만든 다음 코드로 옮기는 것이 편하다. 물론 머리 속으로 생각하는것만으로도 슥삭해버리는 사람들도 있지만 그게 당신과 나는 아니니까 최대한 종이에 써놓고 시작해보자. 시험장에서 주는 연습지 괜히 주는거 아니다.

먼저 큰 틀을 보자.

  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.

너무 간단해보인다는 생각이 들 것이다. 특히 1,2는 단순히 2차원배열의 맨 왼쪽 위부터 오른쪽위까지 한칸씩 이동하면서 해당하는 열 하나를 위에서 아래로 보면되니 생각할 것도 없어보인다.
보통 여기까지 생각하고 쉬운문제네 하면서 짜다가 3번에서 고민에 빠지게 되는데, 3번을 조금 더 자세히 살펴봐보자.

3-1. 모든 상어가 자신이 보고있는 방향으로 정해진 속력만큼 이동한다. 이 때 벽을 만나면 방향을 바꿔서 이동한다.
3-2. 이동을 마치고 같은 칸에 여러 마리의 상어가 있다면 가장 큰 상어가 나머지를 전부 잡아먹는다.

모든 상어를 한 칸씩 움직인다면 바로 시간초과를 받으니 한 번에 상어를 움직일 방법을 생각해야한다. 규칙을 찾기 위해 실제로 상어를 움직여보면

위에서 A상어가 제자리로 돌아오는데 2*(C-1)번의 이동이 (C=열의 개수) 필요한 것이 보인다. 따라서 가로로 움직이는 상어들은 속력을 mod 2*(C-1) 해주고 세로로 움직이는 상어들은 속력을 mod 2*(R-1) 해줄 수 있다.

그 다음으로 상어가 배열 칸을 넘어갔을 때 반대로 이동하게 해야하는데 아래 그림에서 C 상어가 배열 칸을 넘어서 왼쪽으로 이동했다고 생각하면

0-based index라 생각하면 (1,-5)의 위치에 가게되는데 이를 0번열을 기준으로 오른쪽으로 뒤집어버리면 원래 가야할 위치인 (1, 5) 위치로 이동하게되고 이동방향만 왼쪽에서 오른쪽으로 바꾸어주면된다. 즉, 현재위치가 음수면 그대로 양수로 바꿔주면 되고, 0쪽이 아니라 R혹은 C를 넘어섰을때도 같은 방식으로 뒤집어주면 되는데 이 때 위에서 속력을 모두 mod 2*(R-1)을 해주었으므로 최대 2번만 뒤집으면 상어의 이동은 끝난다.

다음으로 이동 이후 한 칸에 가장 크기가 큰 상어만 남아있게해야하는데 그림에서 보이는 것처럼 그냥 이차원배열에 상어를 넣어서 관리할 경우 상어를 이동하면서 처리하기가 귀찮아지므로 상어는 따로 배열을 만들어서 관리하고 이차원배열은 서로 겹치는지 여부만 판별하는 용도로 하였다.

여기까지 생각했다면 이제 코드를 보자.

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

struct Shark
{
    // f = 현재 이 상어가 살아있는지 저장하는 flag( 1=생존, 0=사망 )
	int r, c, s, d, z, f;
	bool operator<(Shark& s)
	{
		return z < s.z;
	}
};

int R, C, M, ans, arr[110][110], dn[] = { -1,1,0,0 }, dm[] = { 0,0,1,-1 };
Shark shark[10'010];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> R >> C >> M;
	for (int i = 1; i <= M; ++i)
	{
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		r--, c--, d--;
		arr[r][c] = i;
		shark[i] = { r,c,s,d,z,1 };
	}
    // 1. j = 현재 낚시왕의 위치(0->C-1)
	for (int j = 0; j < C; ++j)
	{
        // 2. 위에서부터 가장 가까운 상어를 제거
		for (int i = 0; i < R; ++i)
		{
			if (arr[i][j]) 
			{ 
				ans += shark[arr[i][j]].z; 
				shark[arr[i][j]].f = 0; 
				break;
			}
		}
        // 3. 상어 이동
        // 모든 상어 정보는 shark[] 배열에 있으므로 이동시작시 arr배열은 다 지워준다.
		for (int i = 0; i < R; ++i)
			for (int j = 0; j < C; ++j)
				arr[i][j] = 0;
		for (int i = 1; i <= M; ++i)
		{
			auto& sh = shark[i];
			if (sh.f == 0) continue;
            // nn, nm = 맵의 경계를 생각하지 않고 움직였을 때의 상어의 행,열 위치 
			int nn = sh.r + ((sh.s * dn[sh.d])%(2*(R-1))), nm = sh.c + ((sh.s * dm[sh.d])%(2*(C-1)));
            // nn, nm이 경계를 넘어섰을 경우 뒤집어주자
			for (int tmp = 0; tmp < 2; ++tmp)
			{
				if (nn < 0) { nn = abs(nn); sh.d = 1; }
				if (nn >= R) { nn = R - (nn - R + 2); sh.d = 0; }
				if (nm < 0) { nm = abs(nm); sh.d = 2; }
				if (nm >= C) { nm = C - (nm - C + 2); sh.d = 3; }
			}
			sh.r = nn; sh.c = nm;
            // 이동한 곳에 상어가 있을 경우 크기가 큰 상어만 남겨준다.
			if (arr[nn][nm])
			{
				auto& sh2 = shark[arr[nn][nm]];
				if (sh < sh2) { sh.f = 0; }
				else { sh2.f = 0; arr[nn][nm] = i; }
			}
			else arr[nn][nm] = i;
		}
	}
	cout << ans;
}