[백준 23290][C++] 마법사 상어와 복제

문제

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

23290번: 마법사 상어와 복제

 

풀이 과정

1. 현재 저장되어 있는 물고기들의 상태를 복사한다. (이후 모든 과정을 수행 후 fish_map에 추가)

2. 물고기들을 조건에 맞게 이동시킨다.

3. 상어의 이동할 경로를 DFS를 통해 찾은 후, 이동시킨 상태를 fish_map에 반영한다.

4. 물고기를 먹은 흔적인 냄새를 감소시킨다.

5. 복사했던 물고기들을 fish_map에 추가한다.

6. 1-5 과정을 S번 반복한 뒤의 물고기의 총마릿수를 출력한다.

 

세부 풀이

해당 문제에서 중요하다고 생각했던 부분은 DFS를 통해 방문할 때 방문했던 칸을 다시 방문할 수 있다는 점이다. 만약 상어의 시작 위치에 물고기가 같이 존재한다면 다른 칸으로 이동했던 상어가 시작 칸으로 돌아오는 방법이 가장 많은 물고기를 먹을 수 있는 경우일 수 있다. 따라서 이를 반영하도록 구현해야 한다. 

 

(1)

물고기들은 vector <int> fish_map [5][5]를 이용하여 저장했다. 이중 벡터의 index가 위치 정보가 되며, 벡터 안에는 방향 정보만 입력한다.

one_cycle 함수 내부에서 copy_fish_map을 이용하여 원래 물고기들의 상태를 저장했다.(Line 126)

 

(2) move_fish 함수

fish_map에 저장되어있는 방향 정보를 기준으로 물고기의 이동을 수행하는 함수이다. 이때 이동 한 물고기를 한번 더 이동시키는 경우를 막기 위해 이동 한 물고기들은 새로운 move_fish_map 벡터에 저장한 뒤 업데이트하는 방식을 이용했다. 방향 정보로 물고기가 이동할 수 있다면 이동하고, 그렇지 않다면 반시계 45도만큼의 방향 변경을 진행한다. 이 방향 변경은 총 8번까지 수행하는데, 8번이 모두 수행된 경우는 모든 방향으로 진행할 수 없는 상황이므로 원래 방향을 유지하여 move_fish_map 벡터에 저장한다. 최종적으로 모든 물고기들의 이동이 끝난 후 move_fish_map 벡터를 fish_map 벡터에 업데이트한다.

 

(3) dfs 함수 / move_shark 함수

dfs를 수행하면 문제의 조건에 맞는 방식이 dfs_ans에 저장된다.

 

dfs를 통해 방문하며 각 순서를 어떻게 보존할지가 관건이었다. 이전의 다른 코드를 작성할 때는 dfs에 대한 이해도 낮아서, 벡터와 next_permutation을 이용하여 완전 탐색을 수행했다. 하지만 이 문제에서는 dfs를 통해 현재 방문 상태를 dfs_temp에 저장하며 진행하다 dfs의 depth(=cnt)가 원하는 값에 도달했을 때의 방문 상태를 dfs_ans에 업데이트하는 방식을 사용했다. 

 

DFS의 1 1 1 / 1 1 2 / 1 1 3 / 1 1 4 / 1 2 1... 과 같은 방식으로 사전 순으로 탐색한다는 특징을 이용했다.

문제에서는 가장 많은 물고기를 잡아먹으면서 사전 순으로 가장 빠른 방식을 채택한다는 조건이 있었다. 이는 DFS로 방문하며 max 값보다 클 때만 업데이트하는 경우로 처리할 수 있다. max값보다 클 때만 업데이트를 진행한다면 max값과 같은 경우들 중 가장 먼저 방문하는 방법을 이용하는 것이기 때문이다.

 

여기서 그치지 않고 이 문제에서는 DFS를 통해 방문했던 칸을 다시 방문할 수 있다. 그런 경우 물고기의 양이 더 많은 경우가 존재한다. 따라서 visited 배열을 통해 방문 여부를 남기며, 방문을 했었다면 숫자를 추가하지 않고 이동하도록 구현했다.

 

move_shark 내부에서는 dfs를 수행하여 dfs_ans에 현재 상태에서의 최적의 경로를 저장한다.

저장된 최적의 경로로 이동하며 경로에 있는 물고기들을 모두 먹어치운다. 이때 물고기가 있던 칸은 물고기의 냄새가 남게 되며, 물고기가 없었다면 냄새가 남지 않게 되는 상황을 반영하도록 코드를 구현했다. 조건에서 두 번 전 연습에서 생긴 냄새가 사라진다고 되어있으므로 총 3번째 과정이 지난 후에야 냄새가 사라진다. 경로를 이동한 최종 위치를 상어의 위치에 저장한다.

 

(4)

one_cycle 내부에서 map에 저장되어 있는 0보다 큰 냄새 정보들을 1씩 감소시킨다.

 

(5)

one_cycle 내부에서 copy_fish_map에 저장되어 있던 초기 물고기 상태를 move_fish, move_shark 가 수행된 상태에 추가한다.

 

(6)

onec_cycle을 S번 반복한 뒤 최종적인 물고기의 마릿수를 출력한다.

 

 

소스 코드

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

struct shark{
    int x,y;
};

shark shk;

int M,S;
int map[5][5];
vector<int> fish_map[5][5];

int dir[9][2]={{0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};

void Input(){
    cin >> M >> S;
    int x,y,d;
    for(int i=0; i<M; i++){
        cin >> x >> y >> d;
        fish_map[x][y].push_back(d);
    }

    cin >> shk.x >> shk.y;
}

void move_fish(){    
    vector<int> move_fish_map[5][5];
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=0;k<fish_map[i][j].size();k++){
                int cur_dir = fish_map[i][j][k];
                int cnt = 8;
                while(cnt--){
                    int nx=i+dir[cur_dir][0];
                    int ny=j+dir[cur_dir][1];
                    //범위 벗어나거나, 냄새가 남아있거나, 상어 위치라면 방향 바꾼다.
                    if((nx < 1 || nx > 4 || ny < 1 || ny > 4) || 
                       (map[nx][ny]>0)   || (nx == shk.x && ny == shk.y)){
                        cur_dir--;
                        if(cur_dir==0) cur_dir = 8;
                    }
                    else{
                        move_fish_map[nx][ny].push_back(cur_dir);
                        break;
                    }
                }
                //한바퀴 다 돌아도 없는 경우 그대로 넣는다.
                if(cnt<0){
                    move_fish_map[i][j].push_back(fish_map[i][j][k]);
                }
            }
        }
    }

    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            fish_map[i][j] = move_fish_map[i][j];
        }
    }
}

int dfs_max=0;
int dfs_temp[3];
int dfs_ans[3];
int dfs_dir[5][2] = {{0,0},{-1,0},{0,-1},{1,0},{0,1}};
bool dfs_visited[5][5];
void dfs(int x, int y, int sum, int cnt){
    if(cnt==3){
        if(dfs_max < sum){
            dfs_max = sum;
            memcpy(dfs_ans, dfs_temp, sizeof(dfs_temp));
        }
        return;
    }

    for(int i=1;i<=4;i++){
        int nx = x+dfs_dir[i][0];
        int ny = y+dfs_dir[i][1];
        if(nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
        dfs_temp[cnt] = i;
        int num_fish = fish_map[nx][ny].size();
        if(dfs_visited[nx][ny]){
            dfs(nx,ny,sum,cnt+1);
        }
        else{
            dfs_visited[nx][ny] = true;
            dfs(nx,ny,sum+num_fish,cnt+1);
            dfs_visited[nx][ny] = false;
        }
    }

}

void move_shark(){
    //dfs 전 초기화 과정
    dfs_max = -1;
    for(int i=0;i<3;i++) {
        dfs_ans[i]=1;
        dfs_temp[i]=1;
    }
    memset(dfs_visited,false,sizeof(dfs_visited));

    dfs(shk.x,shk.y,0,0);

    //dfs 이후에는 dfs_ans 에 사전순으로 빠르며 가장 많은 물고기를 잡는경로가 저장됨
    int nx = shk.x;
    int ny = shk.y;
    for(int i=0;i<3;i++){
        nx+=dfs_dir[dfs_ans[i]][0];
        ny+=dfs_dir[dfs_ans[i]][1];
        if(fish_map[nx][ny].size()!=0){
            fish_map[nx][ny].clear();
            //냄새
            map[nx][ny] = 3;
        }
    }
    shk.x = nx;
    shk.y = ny;
}

void one_cycle(){
    vector<int> copy_fish_map[5][5];
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            copy_fish_map[i][j] = fish_map[i][j];
        }
    }
    move_fish();
    move_shark();
    //냄새 1 감소
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            if(map[i][j]>0) map[i][j]--;
        }
    }
    //복제
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=0;k<copy_fish_map[i][j].size();k++){
                fish_map[i][j].push_back(copy_fish_map[i][j][k]);
            }
        }
    }
}

void solve(){
    while(S--){
        one_cycle();
    }
    int ans = 0;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            ans += fish_map[i][j].size();
        }
    }

    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Input();
    solve();

    return 0;
}

 

 

결과 및 후기

구현하는 도중 벡터를 memcpy를 통해 복사하는 실수를 했었다. 실행되며 초기화되지 않은 임의의 값들이 입력되어 인덱스를 벗어나는 오류가 발생했다. 이와 함께 C++에서는 std::copy를 이용하면 memcpy와 같은 기능을 수행할 수 있다는 사실을 알게 되었다.