BOJ 17143 낚시왕

작성일 | In |

Problem : 낚시왕

유형 : 구현

문제 해석

  • 낚시왕이 잡은 상어 크기의 합을 구하라.

문제 재해석

  • 구현 문제이다. 시키는 대로 구현한다.
  • 땅에 가장 가까운 상어를 잡는다.
  • 상어는 동시에 움직인다.
  • 낚시왕이 움직여 다시 상어를 잡는다.

해결 전략

  • 상어는 한정된 공간 안에서 계속 움직인다.
  • 속도가 1000이면 for문을 1000번 돌리지 않고, mod 연산을 통해 불필요한 반복 이동을 줄인다.

설계, 구현

  • 만약 위로 움직일 때 맵 크기가 3이라면
  • (n - 1) * 2 만큼 움직이면 , 방향과 위치가 원위치 된다.
  • 이점을 이용하여 speed에 mod연산을 취해 이동 거리를 줄여 주었다.
    • speed = speed % (n - 1) * 2
  • 상어들은 전부 동시에 움직이니, 큐를 이용해 미리 담아두고 한번에 처리하였다.
  • visit 배열을 두고, 해당 공간에 상어가 존재하는지 유무를 따졌다.

주의할 점

  • 상하 좌우 순으로 입력이 들어오지 않는다. 좌표 재 설정이 필요하다.
  • 상어는 동시에 움직이고, 마지막에 도착한 공간에서 겹칠 경우에만 서로를 먹는다.
  • 속도를 줄여서 불필요한 이동 연산을 제거해야 한다.
    • 속도가 1000까지 가능하므로, mod연산이 없을 시 최악의 경우 매번 1000번의 연산이 추가된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
#define spot pair<int,int>
using namespace std;

struct shark {
    int speed;
    int dir;
    int _size;
};

const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };

shark water[102][102];
bool visit[102][102];


queue<pair<spot, shark>> move_q;

int n, m, shark_n;

void Get_New_Spot() {
    while (!move_q.empty()) {
        auto cur = move_q.front(); move_q.pop();
        spot cur_spot = cur.first;
        shark cur_shark = cur.second;

        if (visit[cur_spot.first][cur_spot.second]) {
            shark spot_shark = water[cur_spot.first][cur_spot.second];
            if (spot_shark._size > cur_shark._size) continue;
        }
        visit[cur_spot.first][cur_spot.second] = true;
        water[cur_spot.first][cur_spot.second] = cur_shark;
    }
}

void Move(int x, int y, shark k) {
    int cur_dir = k.dir;
    int nx = x;
    int ny = y;

    for (int i = 0; i < k.speed; ++i) {
        nx = nx + dx[cur_dir];
        ny = ny + dy[cur_dir];

        if (nx < 0 or nx >= n or ny < 0 or ny >= m) {
            cur_dir = (cur_dir + 2) % 4;
            nx = nx + dx[cur_dir] * 2;
            ny = ny + dy[cur_dir] * 2;
        }
    }

    k.dir = cur_dir;

    move_q.push({ {nx,ny}, k });
}

void Shark_Move() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (!visit[i][ii]) continue;
            visit[i][ii] = false;
            Move(i, ii, water[i][ii]);
        }
    }
    Get_New_Spot();
}


void Solve() {
    int answer = 0;

    for (int king = 0; king < m; ++king) {
        for (int i = 0; i < n; ++i) {
            if (!visit[i][king])continue;
            visit[i][king] = false;
            answer += water[i][king]._size;
            break;
        }
        Shark_Move();
    }

    cout << answer << "\n";
}

void Input() {
    cin >> n >> m >> shark_n;

    int s_x, s_y, s, d, z;

    for (int i = 0; i < shark_n; ++i) {
        cin >> s_x >> s_y >> s >> d >> z;

        if (d == 1) d = 0;
        else if (d == 2) d = 2;
        else if (d == 3) d = 1;
        else if (d == 4) d = 3;

        s_x--, s_y--;
        water[s_x][s_y].dir = d;

        if (d == 0 or d == 2) s = s % ((n - 1) * 2);
        else s = s % ((m - 1) * 2);

        water[s_x][s_y].speed = s;
        water[s_x][s_y]._size = z;
        visit[s_x][s_y] = true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 시간 초과가 난 경우, 문제에서 주어진 제한 범위를 잘 살펴보자
  • 그리고 시간 초과가 날만한 부분을 찾고 그 부분을 어떻게 압축하거나 최적화 할 수 있을지 고민해보자.
  • 푸는데 3시간은 걸린것 같다. 나중에 꼭 다시 풀어봐야 할 문제.