본문 바로가기

Programming/BOJ

BOJ 17143 · 낚시왕


알고리즘 분류 : 시뮬레이션  


문제에 주어진 조건을 그대로 구현해야 하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 낚시왕이 움직인 후 상어를 낚는 과정, 두 번째, 모든 상어가 제각기 움직이면서 서로를 잡아먹는 과정이다.


  • 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)




참고



태그