[C++] 낚시왕 (17143번)

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

17143번: 낚시왕

---

문제풀이

골드 1치고 풀만한 문제라고 생각한다. 개인적으로 드래곤 커브 같은 문제들이 더 어려운것 같다. 두 부분으로 나누어 풀어주었다.

1. 낚시꾼이 오른쪽으로 이동해 상어를 낚시한다.

2. 상어가 이동한다.

 

상어를 저장하기 위해 구조체를 선언하여 사용하였다.

1번은 매우 쉽게 구현할 수 있다. 그냥 열 반복하면서 상어를 찾으면 정답에 크기만큼 더해주고 상어를 없애면 된다.

 

2번 구현이 좀 어려웠다. 상어가 벽에 닿으면 방향을 바꾸어 이동하는 것인데 한번에 계산하는 방법을 떠올리지 못해서 벽에 닿는 순간을 기준으로 분기를 쳐서 반복문으로 구현했다.

if(direction == 1) {
    if(speed < row) {
        row -= speed;
        break;
    }
    speed -= row;
    row = 2;
    direction = 2;
}

 

위로 가는 상어의 예시이다. 만약 남은 speed(가야할 거리)가 현재 상어의 row 위치보다 작다면 그냥 row에서 speed를 빼주면 그곳이 상어의 위치가 된다.

그게 아니라 speed가 더 높다면 방향을 전환해주고 상어의 위치를 전환된 위치의 처음(방향을 바꾸는 위치)으로 놔준다. 이런 방식으로 4 방향을 구현하면 반복문을 돌면서 상어가 알맞은 위치에 이동한다.

그리고, 이동한 위치에 다른 상어가 있는지 체크하고 알맞은 상어를 임시저장해주면 된다.

 

#include <iostream>

using namespace std;

int r, c, m;
int answer;

struct Shark {
    int size;
    int direction;
    int speed;
};

Shark arr[101][101];

void findShark(int c) {
    for(int i=1; i<=r; i++) {
        if(arr[i][c].size != 0) {
            answer += arr[i][c].size;
            Shark shark = {0, 0, 0};
            arr[i][c] = shark;
            break;
        }
    }
}

void moveShark() {
    Shark arr2[101][101];
    for(int i=1; i<=r; i++) {
        for(int j=1; j<=c; j++) {
            Shark shark = {0, 0, 0};
            arr2[i][j] = shark;
        }

    }

    for(int i=1; i<=r; i++) {
        for(int j=1; j<=c; j++) {
            if(arr[i][j].size > 0) {
                int direction = arr[i][j].direction;
                int speed = arr[i][j].speed;
                int row = i;
                int col = j;
                while(true) {
                    if(direction == 1) {
                        if(speed < row) {
                            row -= speed;
                            break;
                        }
                        speed -= row;
                        row = 2;
                        direction = 2;
                    }
                    else if(direction == 2) {
                        if(row+speed <= r) {
                            row += speed;
                            break;
                        }
                        speed = speed - (r-row+1);
                        row = r-1;
                        direction = 1;
                    }
                    else if(direction == 3) {
                        if(col+speed <= c) {
                            col += speed;
                            break;
                        }
                        speed = speed - (c-col+1);
                        col = c-1;
                        direction = 4;
                    }
                    else {
                        if(speed < col) {
                            col -= speed;
                            break;
                        }
                        speed -= col;
                        col = 2;
                        direction = 3;
                    }
                }
                // cout << i << " " << j << " " << row << " " << col << "  " << arr2[i][j].size << " " << arr2[row][col].size << endl;
                if(arr2[row][col].size != 0) {
                    if(arr[i][j].size > arr2[row][col].size) {
                        arr2[row][col].size = arr[i][j].size;
                        arr2[row][col].speed = arr[i][j].speed;
                        arr2[row][col].direction = direction;
                    }
                }
                else {
                    arr2[row][col].size = arr[i][j].size;
                    arr2[row][col].speed = arr[i][j].speed;
                    arr2[row][col].direction = direction;
                }
            }
        }
    }
    for(int i=1; i<=r; i++) {
        for(int j=1; j<=c; j++) {
            arr[i][j] = arr2[i][j];
        }
    }
}

int main() {
    cin >> r >> c >> m;
    for(int i=0; i<m; i++) {
        int a, b, s, d, z;
        cin >> a >> b >> s >> d >> z;
        Shark shark = {z, d, s};
        arr[a][b] = shark;
    }

    for(int i=1; i<=c; i++) {
        findShark(i);
        moveShark();
        // for(int i=1; i<=r; i++) {
        //     for(int j=1; j<=c; j++) {
        //         cout << arr[i][j].size << " ";
        //     }
        //     cout << endl;
        // }
        // cout << endl;
    }

    cout << answer;
    return 0;
}

주의할점은 moveShark 함수에서, Shark arr2[101][101]로 선언해서 임시 배열을 만들어 사용하였는데, 이게 함수 호출이 끝나도 값이 그대로 살아있다. 그래서 함수 실행마다 초기화를 시켜주어야 한다.

이게 그리고 반복문을 쓰더라도 시간초과가 터지지 않는 이유는 만약 속도가 1000이라고 치면, 배열의 크기가 커지면 반복 횟수가 줄어들고, 배열의 크기가 작아지면 반복의 횟수가 늘어나기 때문에 상쇄되어 시간초과가 나지 않는다.

 

속도를 줄이는 방법은 반복없이 1회만에 찾는 방법정도가 있는것 같다.

 

다른 사람 풀이를 참고해 보니 반복을 더 줄이는 방법이 있는데 speed % (R-1)*2 를 사용해 speed 값을 줄이고 계산하는 것이다. (R-1)*2 -> 이 값이 바로 다시 원래 위치로 돌아오는데 필요한 이동 수이다.