[백준] 23290번: 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

이번에는 복제 연습을 하는 귀여운 마법사 상어!ㅎㅎ

 

소요 시간

골드 2 기준으로 1시간 40분이 소요되었습니다.

 

다른 유저들의 평가

구현할 것이 많다, 상어의 3연속 이동을 구현할 때 주의할 것이 많으므로 실수하기 쉽다.

 

구상

그냥 구현 문제이기 때문에 시키는 대로 구현했습니다.

1. 물고기의 이동 함수(point : 이동 후 물고기와 이동 전 물고기가 꼬여서 두번 이동하지 않게 따로 배열을 생성하는것)

2. 상어의 이동 경로를 구하는 함수(point : dfs경로찾기, 어떤 칸을 재방문하는 경로라도 물고기만 많이 잡으면 된다는 것에 주의)

3. 냄새를 지우는 함수

4. 복제를 완료시키는 함수

 

어려웠던 점

아 상어 이동 경로를 구하는 함수를 잘못 짜는 바람에 디버깅을 좀 했습니다. 섣불리 어떤 칸을 재방문한다면 그 경로는 최대의 물고기를 잡는 경로가 아니라고 판단한 점이 패인이었습니다.

그래도 특정 케이스에서 자꾸 물고기 수가 더 많이 남아 있다고 나와서, 그렇다면 물고기 수를 줄이는 상어 이동 관련 함수가 잘못되었구나라고 빠르게 판단하고 디버깅할 수 있었습니다.

여러모로 아쉬운 점이 많은 문제였습니다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int fdx[8] = {0,-1,-1,-1,0,1,1,1};
int fdy[8] = {-1,-1,0,1,1,1,0,-1};

int sdx[4] = {-1,0,1,0};
int sdy[4] = {0,-1,0,1};

int max_fishes = 0;
vector<int> shark_path;
bool visited[4][4];

void finish_dup(vector<vector<vector<int> > >& prev, vector<vector<vector<int> > >& now) {
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            now[i][j].insert(now[i][j].end(), prev[i][j].begin(), prev[i][j].end());
        }
    }
}

void move_fishes(vector<vector<vector<int> > >& fishes, pair<int, int> shark, vector<vector<int> >& smell) {
    vector<vector<vector<int> > > moved_fishes(4, vector<vector<int> >(4, vector<int>()));

    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            for(int k=0; k<fishes[i][j].size(); k++) {
                int d = fishes[i][j][k];
                int nx = i + fdx[d]; int ny = j + fdy[d];
                int cnt = 0;
                while(nx > 3 || nx < 0 || ny > 3 || ny < 0 || (shark.first == nx && shark.second == ny) || smell[nx][ny] != 0) {
                    d += 7; d %= 8;
                    nx = i + fdx[d]; ny = j + fdy[d];
                    cnt ++;
                    if (cnt == 8) break;
                }
                if(cnt == 8) {
                    //don't move
                    moved_fishes[i][j].push_back(fishes[i][j][k]);
                }
                else {
                    moved_fishes[nx][ny].push_back(d);
                }
            }
        }
    }

    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            fishes[i][j] = moved_fishes[i][j];
        }
    }

    return;
}

void make_path(vector<vector<vector<int> > >& fishes, pair<int, int> shark, int sum, vector<int> path) {
    if(path.size() == 3) {
        if(sum > max_fishes || shark_path.empty()) {
            max_fishes = sum;
            shark_path = path;
        }
        return;
    }
    for(int i=0; i<4; i++) {
        int nx = shark.first + sdx[i]; int ny = shark.second + sdy[i];
        if(nx < 0 || nx > 3 || ny < 0 || ny > 3) continue;
        path.push_back(i);
        if(visited[nx][ny] == false) {
            visited[nx][ny] = true;
            make_path(fishes, pair<int, int>(nx, ny), sum + fishes[nx][ny].size(), path);
            path.pop_back();
            visited[nx][ny] = false;
        }
        else {
            make_path(fishes, pair<int, int>(nx, ny), sum, path);
            path.pop_back();
        }
    }
}

pair<int, int> move_shark(vector<vector<vector<int> > >& fishes, pair<int, int> shark, vector<vector<int> >& smell) {
    for(int i=0; i<3; i++) {
        shark.first += sdx[shark_path[i]]; shark.second += sdy[shark_path[i]];
        if(fishes[shark.first][shark.second].size() != 0) {
            fishes[shark.first][shark.second].resize(0);
            smell[shark.first][shark.second] = 3;
        }
    }
    return shark;
}

void remove_smell(vector<vector<int> >& smell) {
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            if(smell[i][j] != 0) smell[i][j] -= 1;
        }
    }    
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int M, S;
    cin >> M >> S;
    vector<vector<vector<int> > > fishes(4, vector<vector<int> >(4, vector<int>()));
    vector<vector<int> > smell(4, vector<int>(4, 0));
    pair<int, int> shark;
    for(int i=0; i<M; i++) {
        int fx, fy, d;
        cin >> fx >> fy >> d;
        fishes[fx-1][fy-1].push_back(d-1);
    }
    cin >> shark.first >> shark.second;
    shark.first -= 1; shark.second -= 1;

    for(int i=1; i<=S; i++) {
        //step 2.
        vector<vector<vector<int> > > prev(fishes);
        move_fishes(fishes, shark, smell);
        //step 3.
        vector<int> path; shark_path.resize(0); max_fishes = 0;
        for(int i=0; i<4; i++) fill_n(visited[i], 4, false);
        make_path(fishes, shark, 0, path);
        shark = move_shark(fishes, shark, smell);
        //step 4.
        remove_smell(smell);
        //step 5.
        finish_dup(prev, fishes);
    }
    int answer = 0;
    for(int i=0; i<fishes.size(); i++) {
        for(int j=0; j<fishes[i].size(); j++) {
            answer += fishes[i][j].size();
        }
    }
    cout << answer << endl;
    
    return 0;
}