반응형
알고리즘 분류 : 시뮬레이션
문제에 주어진 조건을 그대로 구현해야 하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 낚시왕이 움직인 후 상어를 낚는 과정, 두 번째, 모든 상어가 제각기 움직이면서 서로를 잡아먹는 과정이다.
- 1. 낚시왕은 매 턴마다 한 칸 움직인 후, 상어 한 마리를 낚는다.
- 먼저 낚시왕이 한 칸 앞으로 이동한다. 낚시왕은 최대 R(열의 개수)번 움직일 수 있다.
- 도착한 열에서 땅에 가장 가까운 상어 한 마리를 낚는다. 땅에 가장 가까운 상어는 0에 가까운 행(C)에 위치한다.
- 2. 상어가 제각기 주어진 속도와 방향에 따라 움직이고, 자신보다 작은 상어를 잡아먹는다.
- 상어의 속도는 움직일 수 있는 칸의 개수를 의미한다. 가장자리에 도달하면 방향을 바꿔서 남은 횟수만큼 움직여야 한다.
- 매번 한 칸씩 움직이는 것은 비효율적이므로, 규칙을 찾는 것이 좋다. X에서 출발했다고 가정하면, 움직이다가 결국은 X로 돌아오게 되어있다. 즉, 같은 움직임을 주기적으로 반복한다.
- 속도를 S, 맵의 크기를 R * C 라고 하자. 단, 맵의 인덱스 범위는 [0, 0] ~ [R-1, C-1] 이다.
- 위/아래로 움직일 때는 S % ((R-1)*2) 만큼 반복된다. 왼/오른쪽으로 움직일 때는 S % ((C-1)*2) 만큼 반복된다.
- 구한 주기만큼 움직이면서, 가장자리에 부딪히면 방향을 바꾼다. 위(0) ↔ 아래(1), 오른쪽(2) ↔ 왼쪽(3)
- 움직임을 마친 후, 도착한 위치에 자신보다 큰 상어가 있는지 확인한다. 이때, 이미 이동을 마친 상어와 크기를 비교해야 한다. 이를 위해 별도의 맵을 만들어 둘 필요가 있다. A는 원래 상어가 위치한 맵이며, B는 상어의 이동을 저장할 맵이다.
- 자신보다 큰 상어가 없다면, 이동한 상어의 값을 B에 저장한다. 원래 상어가 위치한 A의 값은 0으로 초기화한다.
- 모든 상어의 이동을 마친 후, B에 들어있는 모든 값을 A에 복사한다.
C++ 소스코드
#include <cstdio> #include <cstring> struct shark { int s, d, z; }; int r, c, m, ans; shark a[100][100]; const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1}; void solve() { for (int t=0; t<c; t++) { shark b[100][100] = {0}; // Fishing a shark for (int i=0; i<r; i++) { if (a[i][t].z) { ans += a[i][t].z; a[i][t] = {0, 0, 0}; break; } } // Sharks move for (int i=0; i<r; i++) { for (int j=0; j<c; j++) { if (a[i][j].z) { if (a[i][j].d < 2) { // Up, Down int s = a[i][j].s % ((r-1)*2); int d = a[i][j].d; int ni = i; while (s--) { if (ni == 0 && d == 0) d = 1; if (ni == r-1 && d == 1) d = 0; ni += dx[d]; } if (a[i][j].z > b[ni][j].z) b[ni][j] = {a[i][j].s, d, a[i][j].z}; } else { // Right, Left int s = a[i][j].s % ((c-1)*2); int d = a[i][j].d; int nj = j; while (s--) { if (nj == 0 && d == 3) d = 2; if (nj == c-1 && d == 2) d = 3; nj += dy[d]; } if (a[i][j].z > b[i][nj].z) b[i][nj] = {a[i][j].s, d, a[i][j].z}; } a[i][j] = {0, 0, 0}; } } } memcpy(a, b, sizeof(b)); } } int main() { scanf("%d %d %d", &r, &c, &m); for (int i=0; i<m; i++) { int x, y, s, d, z; scanf("%d %d %d %d %d", &x, &y, &s, &d, &z); a[x-1][y-1] = {s, d-1, z}; } solve(); printf("%d\n", ans); return 0; }
Python 3 소스코드
r, c, m = map(int, input().split()) a = [[[0, 0, 0] for _ in range(c)] for _ in range(r)] for _ in range(m): x, y, s, d, z = map(int, input().split()) a[x-1][y-1] = [s, d-1, z] dx, dy, ans = (-1, 1, 0, 0), (0, 0, 1, -1), 0 for t in range(c): b = [[[0, 0, 0] for _ in range(c)] for _ in range(r)] for i in range(r): _, _, z = a[i][t] if z: ans += z a[i][t] = [0, 0, 0] break for i in range(r): for j in range(c): s, d, z = a[i][j] if z: if d < 2: ns, nd, ni = s % ((r-1)*2), d, i for _ in range(ns): if ni == 0 and nd == 0: nd = 1 if ni == r-1 and nd == 1: nd = 0 ni += dx[nd] _, _, bz = b[ni][j] if z > bz: b[ni][j] = [s, nd, z] else: ns, nd, nj = s % ((c-1)*2), d, j for _ in range(ns): if nj == 0 and nd == 3: nd = 2 if nj == c-1 and nd == 2: nd = 3 nj += dy[nd] _, _, bz = b[i][nj] if z > bz: b[i][nj] = [s, nd, z] a[i][j] = [0, 0, 0] a = b[:] print(ans)
참고
- 백준 온라인 저지 : BOJ 17143
반응형