[백준 17143][C++] 낚시왕

문제

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

17143번: 낚시왕

 

 

풀이 과정

1. 상어를 저장하기 위한 방법 설정

    상어 구조체를 작성 struct shark {int speed; int dir; int size}

    상어의 좌표는 배열 형태로 저장한다. (한 칸에 하나의 상어만 존재하기 때문에)

2. 낚시로 상어를 잡는 함수

    낚시가 성공했을 때 전역 변수 ans에 상어의 size를 더해주고 해당 칸의 상어를 제거한다.

3. 낚시가 끝난 후 상어의 이동을 진행하는 함수

4. 2번~3번 과정을 각 열마다 반복한다.

5. 최종적으로 전역 변수 ans 값을 출력한다.

 

 

세부 풀이

(1)

초기 구현 때는 상어 구조체에 위치 정보까지 집어넣어 struct shark {int x; int y; int speed; int dir; int size}로 구현한 뒤, 상어들을 queue에 넣어 관리하려고 했었다. 하지만 queue 자료구조 특성상 중간에 위치한 인자의 접근과 수정이 힘들었고, 정렬 후 사용하는 방식을 고려했을 때 낚시왕이 각 열마다 이동하므로 정렬 기준이 계속 바뀌어 효율적이지 않았다.

 

따라서 이중 배열을 이용하여 각 위치에 하나의 상어를 저장하기로 결정했다. (같은 칸에 존재하는 상어는 크기가 큰 상어가 다른 상어를 모두 잡아먹어, 한 칸에 하나의 상어만 존재하기 때문에) 

구조체는 struct shark {int speed; int dir; int size}로 작성했고, 좌표 정보는 이중 배열의 위치를 이용했다.

 

상어의 존재 유무는 상어의 크기를 나타내는 size 변수를 이용했다. 칸의 size 정보가 0이라면 상어가 없는 칸이다. 

 

(2)

낚시로 상어를 잡는 함수는 Column값을 입력받아 해당 Column에 대해서만 탐색을 진행한다. 문제 조건에 의해 땅에서 가장 가까운 상어를 잡는 것이므로 map [index][col]  index 값이 0부터 R-1까지 탐색하며 중간에 상어를 만나면 (size가 0이 아닌 칸을 만나면) 해당 상어의 size를 ans에 저장하고 break 한다. (한 Column당 한 마리의 상어를 잡기 때문에 break)

 

(3)

초기에는 이동할 distance를 상어의 속도 값을 그대로 사용하여 제출했는데, 시간 초과가 발생했다. 상어의 속도가 1000인 경우 각 조건을 확인하며 1000칸을 이동하도록 구현했던 것이다. 하지만 이동하는 구간이 정해져 있기 때문에 이동 후의 위치가 겹치게 된다.

 

예를 들어 아래와 같은 5칸의 초기 상황에서 (S : 상어, 0 : 빈칸)

S 0 0 0 0 

속도가 3인 상어가 1초 동안 이동한 경우에는 0 0 0 S 0의 형태가 될 것이다.

속도가 5인 상어가 1초 동안 이동항 경우에도 0 0 0 S 0의 형태이며,

속도가 11인 경우에도  0 0 0 S 0의 형태이며,

속도가 13인 경우에도 0 0 0 S 0의 형태일 것이다.

 

이렇게 속도가 증가하더라도 최종적으로 이동해야 할 거리는 최대 칸수 미만에서 결정된다. 이를 적용하기 위해서 Row 방향과, Col 방향에 대해 나머지 연산을 통해 최종 이동 거리를 조절하도록 소스코드 Line 51~52에 적용하였다.

 

5칸인 경우에서 속도가 8일 때 1초 뒤의 상황은 처음과 같다. 5칸이 아닌 다른 경우에 동일하게 적용해보니 (R(혹은 C) - 1) * 2라는 공식을 얻을 수 있었다. 이렇게 나머지 연산을 통해, 최대 1000번의 이동을 했던 코드가 0~7번의 이동만 진행하면 되도록 수정될 수 있었다.

 

(4) (5)

이렇게 두 함수를 구현한 뒤, solve라는 함수를 통해 낚시와 이동을 각각 Column 만큼 진행한 후 ans를 출력하도록 구현했다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct shark{
    int speed=0;
    int dir=0;
    int size=0;    
};

const int max_rc = 100;
int R, C, M, ans=0;
shark map[max_rc][max_rc];

void make_shark(int r, int c, int s, int d, int z){
    shark one = {s,d,z};
    map[r][c] = one;
}


void Input(){
    cin >> R >> C >> M;
    int r,c,s,d,z;
    for(int i=0;i<M;i++){
        cin >> r >> c >> s >> d >> z;
        make_shark(r-1,c-1,s,d,z);
    }
}

void catch_shark(int col){
    for(int i=0;i<R;i++){
        if(map[i][col].size == 0) continue;
        ans += map[i][col].size;
        map[i][col] = {0,0,0};
        break;
    }
}

void move_shark(){
    int direction[5][2] = {{0,0},{-1,0},{1,0},{0,1},{0,-1}};
    shark after_move[max_rc][max_rc];
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j].size == 0) continue;
            shark one = map[i][j];
            int x=i;int y=j;
            int distance = one.speed;
            if(one.dir == 1 || one.dir == 2) distance = distance % ((R-1)*2);
            else distance = distance % ((C-1)*2);
            while(distance>0){
                int newX = x+direction[one.dir][0];
                int newY = y+direction[one.dir][1];
                if(newX < 0 || newX >=R || newY <0 || newY >=C){
                    switch (one.dir)
                    {
                    case 1:
                        one.dir = 2;
                        break;
                    case 2:
                        one.dir = 1;
                        break;
                    case 3:
                        one.dir = 4;
                        break;
                    case 4:
                        one.dir = 3;
                        break;
                    default:
                        break;
                    }
                    newX = x+direction[one.dir][0];
                    newY = y+direction[one.dir][1];
                    x=newX; y=newY;
                    distance--;
                }
                else{
                    x=newX; y=newY;
                    distance--;
                }
            }

            if(after_move[x][y].size < one.size)
                after_move[x][y] = one;
        }
    }

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            map[i][j]=after_move[i][j];
        }
    }
}

void solve(){
    for(int i=0;i<C;i++){
        catch_shark(i);
        move_shark();
    }
    cout << ans;
}




int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Input();
    solve();
}

 

결과 및 후기