[백준/Baekjoon] 17143 낚시왕 C++ :: Implementation

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

17143번: 낚시왕

---

1. Logic

낚시꾼이 물고기를 잡고 그 이후에 상어가 이동을 한다. 함수 로직 순서는 이렇고, 이 문제를 풀면서 두번 막혔는데 두개만 잘 생각하면 풀기 쉬운 문제인 것 같다. 두개를 생각하는게 어려워서 그렇지,, (내 기준)

 

1. 배열은 0부터 시작한다.

아주 기초적이지만 이거때문에 상어를 이동하는 로직에서 한번 틀렸다..ㅜ 답이 이상해서 출력해보다가 테케 1번의 3번상어가 배열에서 빠져있었다. 나는 입력을 받을 때 0번배열부터 받지 않고 1번부터 받아서 내 배열은 [1~n]까지 였다.  근데 이동을 할 때 if문 조건에서 [0, n]으로해서 방향을 바꾸는 경우 2번씩을 더 이동해서 틀렸다.

 

2. 이 문제의 핵심 같은데, 문제에서 속력, 즉 상어가 이동하는 횟수가 최대 1000번이다. 나는 상어를 한번씩 전부 이동시키는 로직으로 만들었는데 최악의 경우라면 시간복잡도는 100*100*100*1000(루프반복100번*상어마리수{100*100}*속력) 총 10억이기 때문에 당연히 시간초과이다. 모르겟어서 다른 블로그들의 아이디어를 참고했다. 

 

1,2번과 같이 상, 하로 움직이는 상어의 경우 세로길이인 (r-1)*2마다 똑같은 방향 똑같은 위치 돌아온다. 다시 3, 4번과 같이 좌, 우로 움직이는 상어의 경우 가로길이인 (c-1)*2마다 똑같은 방향 똑같은 위치로 돌아온다. 이것을 활용해서 나머지 연산으로 최소 횟수를 속력으로 넣어줘서 while문 루프 시간을 줄여줬다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

struct shark {
    int y;
    int x;
    int s;
    int d;
    int size;
    int num;
};

int r, c, m;
int ans = 0;

vector<shark> graph[102][102];

void move(int &cury, int &curx, int &dir) {
    if(dir == 1) {
        if(cury - 1 >= 1) {
            cury--;
        }
        else {
            cury++;
            dir = 2;
        }
    }
    else if(dir == 2) {
        if(cury+1 <= r) {
            cury++;
        }
        else {
            cury--;
            dir = 1;
        }
    }
    else if(dir == 3) {
        if(curx+1 <= c) {
            curx++;
        }
        else {
            curx--;
            dir = 4;
        }
    }
    else if(dir == 4) {
        if(curx-1 >= 1) {
            curx--;
        }
        else {
            curx++;
            dir = 3;
        }
    }
}

void start() {
    int fisherIdx = 0;
    
    while(fisherIdx < c) {
        fisherIdx++;
        
        //물고기 잡기
        for(int i = 1; i <= r; i++) {
            if(!graph[i][fisherIdx].empty()) {
                ans += graph[i][fisherIdx][0].size;
                graph[i][fisherIdx].pop_back();
                break;
            }
        }

        vector<shark> temp[101][101];
        
        //물고기 이동
        for(int i = 1; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                if(graph[i][j].empty()) continue;
                
                shark curShark = graph[i][j][0];
                
                int &cury = curShark.y;
                int &curx = curShark.x;
                int moveCnt = curShark.s;
                int &dir = curShark.d;
                
                while(moveCnt--) {
                    move(cury, curx, dir);
                }
                
                if(temp[cury][curx].empty()) {
                    temp[cury][curx].push_back(curShark);
                }
                else {
                    if(temp[cury][curx][0].size < curShark.size) {
                        temp[cury][curx].pop_back();
                        temp[cury][curx].push_back(curShark);
                    }
                }
            }
        }
        
        for(int i = 1; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                graph[i][j] = temp[i][j];
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> r >> c >> m;
    
    for(int i = 0; i < m; i++) {
        int y, x, s, d, z;
        cin >> y >> x >> s >> d >> z;
        if(d == 1 || d == 2) s %= ((r-1) * 2);
        if(d == 3 || d == 4) s %= ((c-1) * 2);
        graph[y][x].push_back({y, x, s, d, z, i+1});
    }
    
    start();
    
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90