백준 g1 23290 마법사 상어와 복제 c++

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

23290번: 마법사 상어와 복제

 

문제 설명

4*4 격자에서 상어가 마법을 연습한다.

격자에는 물고기 M마리가 들어있고, 각각은 이동 방향(8개)를 가진다. 상어도 격자 하나에 들어가 있다.

둘 이상의 물고기가 같은 칸에 있을 수 있고, 마법사 상어와 물고기도 같은 칸에 있을 수 있다.

 

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 이 시점을 저장했다가 5번에서 이루어진다.
2. 모든 물고기가 이동방향대로 1칸씩 이동한다. 
   1. 상어가 있는 칸, 물고기 냄새가 있는 칸, 격자 범위를 벗어나는 칸으로는 이동 불가능하다.
   2. 이동이 불가능하면 반시계방향으로 45도 회전해서 다시 한 칸 이동한다.
   3. 이동할 수 있는 칸이 없으면 이동하지 않는다.
3. 상어가 연속해서 3칸 이동한다. 이때 3칸의 방향은 물고기를 최대로 먹을 수 있는 경우로 한다. 최대로 먹을 수 있는 경우가 여러 개인 경우, 가장 처음의 것 (상 좌 하 우 순서로) 으로 택한다.
   1. 상어는 각 칸에 도착할 때마다 해당 칸의 물고기들을 모두 먹고, 물고기 냄새를 남긴다.
4. 두 턴 전에 생긴 물고기 냄새가 격자에서 사라진다.
5. 1번에서 시전한 복제 마법이 완료되어, 1번 시점의 물고기들이 그대로(위치, 방향) 복제된다.

1~5번의 연습을 S번 했을 때, 남아 있는 물고기의 수를 출력하기

 

풀이

0-1. 저장소

int M, S;
struct fish {
    int x;
    int y;
    int dir;
};
vector<int> board[MAXN][MAXN];
vector<fish> fishInfo; // 이동방향 0 ~ 7, 위치 x, y
vector<fish> replicated;
pair<int, int> sPos;
int smell[MAXN][MAXN];

board에서는 각 칸의 물고기의 번호들을 기록하고, 이 번호를 토대로 fishInfo에서 물고기의 정보(위치, 방향)를 찾을 수 있다.

반대로 fishInfo의 정보로 물고기의 위치를 알 수도 있다.

 

replicated는 1번의 시점을 저장하기 위한 벡터이다. c++에서 벡터는 copy by value이기 때문에 fishInfo와 replicated는 서로 값이 다를 수 있다.

상어의 위치를 저장하기 위한 sPos와 smell의 위치를 저장하기 위한 smell 배열

 

0-2. input

for (int i = 0; i < M; i++) {
    int di, x, y;
    cin >> x >> y >> di;
    --di;
    --x;
    --y;
    fish f = {x, y, di};
    fishInfo.push_back(f);

    board[x][y].push_back(i);
}

그냥 값을 받아서 fishInfo, board에 각각 넣어주면 된다

 

1. 복제 마법 시전

void castMagic() {
    replicated.clear();
    for (fish f : fishInfo) {
        if (f.x == -1) continue;
        replicated.push_back(f);
    }
}

이미 먹힌 물고기는 fish 구조체 값을 모두 -1로 통일해줬기 때문에 제외하고, 나머지를 replicated 벡터에 넣어 현재 시점을 보존한다.

2. 물고기 이동

이미 삭제된 물고기는 제외하고, (값이 -1인 물고기들)

1칸씩 움직여야 한다. 이때 갈 수 없는 위치면 반시계 방향으로 45도씩 돌려야 하므로

for (int pDir = 0; pDir < 8; pDir++) {
    int nDir = (dir - pDir + 8) % 8;
    int nx = x + dx8[nDir];
    int ny = y + dy8[nDir];

    if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
    if (nx == sPos.first && ny == sPos.second) continue;
    if (smell[nx][ny] > 0) continue;

    x = nx;
    y = ny;
    dir = nDir;
    break;
}

 

nDir = (dir - pDir + 8) % 8로 방향을 지정해줬고, 만약 길을 갈 수 없다면 nx, ny로 물고기를 옮기지 않는다.

이렇게 옮겨진 x, y, dir은 board대신 newBoard에 넣어준다. (vector erase를 쓰면 물고기 번호도 찾아야하고, 지우기도 해야해서 O(n^2) 소요)

 

여기서 만약 갈 수 있는 방향을 못 찾았다면, x y dir을 그대로 newBoard에 넣는 셈이다.

newBoard[x][y].push_back(i);
fishInfo[i].x = x;
fishInfo[i].y = y;
fishInfo[i].dir = dir;

 

newBoard에 넣어준 후에는, newBoard의 값을 전역변수인 board에 옮겨준다.

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

 

3. 상어 이동

3-1. 상어가 갈 방향 찾기

상어가 갈 방향은 dfs+백트래킹으로 찾는다.

vector<int> vec; // 현재(dfs)에서 쓸 상어의 방향
int fishCnt = 0; // 지금까지 먹은 물고기 수
int mx = -1; // 최대로 먹은 물고기 수
vector<int> sharkDir; // 최종 상어의 방향
int vis[4][4];

 

함수 인자로는 depth, 현재 상어의 위치 x, y를 받는다.

void dfs(int depth, int x, int y) { // depth번째 vec를 채움

 

만약 depth가 3이면 mx랑 값을 비교하고, 빠져나간다. 

if (depth == 3) {
    if (mx < fishCnt) {
        mx = fishCnt;
        sharkDir = vec;
    }

    return;
}

 

그렇지 않다면 상-좌-하-우 순으로 dfs를 진행한다. 이렇게 하면 가장 사전순으로 빠른 방향을 찾을 수 있다.

(* 사전순이란, 상상상 과 상상하의 먹은 물고기 개수가 같다면, 상상상이 상상하보다 먼저이다)

 

만약 격자 밖으로 삐져나가는 방향이면, 애초에 불가능한 방향이므로 continue를 해준다.

for (int d = 0; d < 4; d++) {
    int nx = x + dx4[d];
    int ny = y + dy4[d];

    if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

    vec.push_back(d);
    if (vis[nx][ny] == 0) fishCnt += board[nx][ny].size();
    vis[nx][ny]++;

    dfs(depth + 1, nx, ny);

    vec.pop_back();
    vis[nx][ny]--;
    if (vis[nx][ny] == 0) fishCnt -= board[nx][ny].size();
}

 

주의할 점 1. vis체크를 하는 이유는 이미 한 번 먹은 물고기를 또 먹지 않기 위해서이다.

예를 들어,

0

0

1

상어 위치

이렇게 세로로 놓여진 격자의 중앙에 물고기가 한 마리 있다고 생각해보자.

그냥 직관적으로 생각해보면 상-상-상이 사전순으로 가장 빠르지만,

vis 체크를 안 하면 상-상-하로 3번째 줄에 있는 물고기를 또 먹는 게 가장 많은 물고기를 먹을 수 있는 경우의 수가 된다.

 

board에 물고기를 지웠다 썼다 할 수도 있지만, 물고기가 여러 마리인 상황에서 그걸 다 지웠다 다시 썼다하는 것보단 vis배열을 둬서 이미 지나간 자리에서는 물고기를 또 먹지 못하도록 하는 게 훨씬 낫다.

 

또한 vis를 boolean으로 둘 수도 있지만, 여러 번 방문한 경우에 vis==true를 false로 되돌리면 안되는데(아직 vis 되돌릴 게 더 남아있음) 되돌리는 경우를 대비해서 int로 선언해주었다.

 

주의할 점 2. vis[nx][ny]의 순서

if (vis[nx][ny] == 0) fishCnt += board[nx][ny].size();
vis[nx][ny]++;

dfs 수행

vis[nx][ny]--;
if (vis[nx][ny] == 0) fishCnt -= board[nx][ny].size();

dfs를 기준으로 대칭이 되도록 해야 한다.

 

3-2. 상어 이동시키기

찾은 상어의 방향대로 이동시킨다. 

만약 이동한 자리에 물고기가 있으면 잡아먹고, smell = 3으로 둔다.

잡아먹힌 물고기의 번호는 fishInfo에서 -1로 초기화해준다.

board [x][y] 역시 초기화해준다.

// 3-2. 상어의 이동
for (int dir : sharkDir) {
    sPos.first = sPos.first + dx4[dir];
    sPos.second = sPos.second + dy4[dir];

    if (board[sPos.first][sPos.second].size() > 0)
        smell[sPos.first][sPos.second] = 3;
    for (int f : board[sPos.first][sPos.second]) {
        fishInfo[f].x = -1;
        fishInfo[f].y = -1;
        fishInfo[f].dir = -1;
    }
    board[sPos.first][sPos.second].clear();
}

 

4. 냄새 제거

void decreaseSmell() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (smell[i][j] > 0) smell[i][j]--;
        }
    }
}

기본값을 3으로 뒀으므로, 이번 턴이 지나고 2턴 후에 smell은 다시 0으로 돌아간다.

 

5. 복제 마법 실행

새로운 fishInfo idx를 만들고, 이를 board에 물고기 번호로 push해준다.

void replicateFish() {
    int idx = fishInfo.size();
    for (fish f : replicated) {
        if (f.x == -1) continue;
        fishInfo.push_back(f);
        board[f.x][f.y].push_back(idx);
        idx++;
    }
}

 

전체 코드

/*boj g1 23290 마법사 상어와 복제*/
#include <iostream>
#include <vector>
#define MAXN 4
using namespace std;

int M, S;
struct fish {
    int x;
    int y;
    int dir;
};
vector<int> board[MAXN][MAXN];
vector<fish> fishInfo; // 이동방향 0 ~ 7, 위치 x, y
vector<fish> replicated;
pair<int, int> sPos;
int smell[MAXN][MAXN];
int dx8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};

void printBoard() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cout << "[\t";
            for (int a : board[i][j]) {
                cout << a << "/" << fishInfo[a].dir << " ";
            }
            cout << "]";
        }
        cout << "\n";
    }
    cout << "===============\n";
}

void printSmell() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cout << smell[i][j] << " ";
        }
        cout << "\n";
    }
}

void printFishInfo() {
    for (int i = 0; i < fishInfo.size(); i++) {
        cout << i << fishInfo[i].dir << "\n";
    }
}

void input() {
    cin >> M >> S;
    for (int i = 0; i < M; i++) {
        int di, x, y;
        cin >> x >> y >> di;
        --di;
        --x;
        --y;
        fish f = {x, y, di};
        fishInfo.push_back(f);

        board[x][y].push_back(i);
    }
    int sx, sy;
    cin >> sx >> sy;
    --sx;
    --sy;
    sPos.first = sx;
    sPos.second = sy;
}

void castMagic() {
    replicated.clear();
    for (fish f : fishInfo) {
        if (f.x == -1) continue;
        replicated.push_back(f);
    }
}

void moveFish() {
    vector<int> newBoard[4][4];
    for (int i = 0; i < fishInfo.size(); i++) {
        int x = fishInfo[i].x;
        int y = fishInfo[i].y;
        int dir = fishInfo[i].dir;

        if (x == -1 && y == -1 && dir == -1) continue; // i번 물고기는 이미 먹힘

        for (int pDir = 0; pDir < 8; pDir++) {
            int nDir = (dir - pDir + 8) % 8;
            int nx = x + dx8[nDir];
            int ny = y + dy8[nDir];

            if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
            if (nx == sPos.first && ny == sPos.second) continue;
            if (smell[nx][ny] > 0) continue;

            x = nx;
            y = ny;
            dir = nDir;
            break;
        }

        newBoard[x][y].push_back(i);
        fishInfo[i].x = x;
        fishInfo[i].y = y;
        fishInfo[i].dir = dir;
    }

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

vector<int> vec;
int fishCnt = 0;
int mx = -1;
vector<int> sharkDir;
int vis[4][4];
void dfs(int depth, int x, int y) { // depth번째 vec를 채움
    if (depth == 3) {
        if (mx < fishCnt) {
            mx = fishCnt;
            sharkDir = vec;
        }

        return;
    }

    for (int d = 0; d < 4; d++) {
        int nx = x + dx4[d];
        int ny = y + dy4[d];

        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        vec.push_back(d);
        if (vis[nx][ny] == 0) fishCnt += board[nx][ny].size();
        vis[nx][ny]++;

        dfs(depth + 1, nx, ny);

        vec.pop_back();
        vis[nx][ny]--;
        if (vis[nx][ny] == 0) fishCnt -= board[nx][ny].size();
    }
}

void moveShark() {
    // 3-1. 상어의 방향 결정
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            vis[i][j] = 0;
    vec.clear();
    sharkDir.clear();
    mx = -1;
    fishCnt = 0;

    dfs(0, sPos.first, sPos.second);
    // cout << mx << "\n";
    // 3-2. 상어의 이동
    for (int dir : sharkDir) {
        sPos.first = sPos.first + dx4[dir];
        sPos.second = sPos.second + dy4[dir];

        if (board[sPos.first][sPos.second].size() > 0)
            smell[sPos.first][sPos.second] = 3;
        for (int f : board[sPos.first][sPos.second]) {
            fishInfo[f].x = -1;
            fishInfo[f].y = -1;
            fishInfo[f].dir = -1;
        }
        board[sPos.first][sPos.second].clear();
    }
}

void decreaseSmell() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (smell[i][j] > 0) smell[i][j]--;
        }
    }
}

void replicateFish() {
    int idx = fishInfo.size();
    for (fish f : replicated) {
        if (f.x == -1) continue;
        fishInfo.push_back(f);
        board[f.x][f.y].push_back(idx);
        idx++;
    }
}

void getAnswer() {
    int answer = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            answer += board[i][j].size();
        }
    }
    cout << answer << "\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    while (S--) {
        // 1. 복제 마법 시전, 현재 fishInfo를 따로 저장
        castMagic();
        // 2. 모든 물고기의 이동
        moveFish();
        //  3. 상어의 이동
        moveShark();

        // 4. 냄새 사라짐
        decreaseSmell();

        // 5. 물고기 복제
        replicateFish();
    }

    // 6. 결과 출력
    getAnswer();
}