BOJ 19236 - 청소년 상어(C++)

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

19236번: 청소년 상어

풀이

상어의 위치는 (0, 0)에서 시작

 

1. 현재위치의 물고기 먹음

   - 먹은 물고기의 번호를 누적 합

   - 먹은 물고기의 방향을 가짐

 

2. 물고기 이동

   - 죽은 물고기는 제외하고 이동

   - 번호가 낮은 물고기부터 이동, 이동하는 위치에 다른 물고기가 있다면 위치 교환

   - 해당 위치로 이동하지 못한다면 45도 반시계 회전 후 탐색

   - 어느 방향으로도 이동하지 못하면 현재 위치 유지

 

3. 상어 이동

   - 상어의 자신의 방향으로 물고기가 없는 칸을 제외하고는 이동가능

   - 이동가능한 모든 경우에 대해  이동 후 1로 실행

   - 이동이 불가능하다면 현재까지 먹은 물고기 순번의 누적합으로 최대값 갱신, 종료 후 대기중인 재귀문 탐색 

 

#include <iostream>
#include <vector>

using namespace std;

int N = 4;
int dy[] = {-1,-1,0,1,1,1,0,-1};
int dx[] = {0,-1,-1,-1,0,1,1,1};
int ans = 0;

struct Fish {
    int y, x, dir;
    bool isdead = false;
};
struct Shark {
    int y, x, dir, cnt=0;
};
void move_shark(vector<vector<int>> map, vector<Fish> fish, Shark shark);

void eat_fish(vector<vector<int>> &map, vector<Fish> &fish, Shark &shark) {
    shark.cnt+= map[shark.y][shark.x];
    shark.dir = fish[map[shark.y][shark.x]].dir;
    //물고기 사망처리
    fish[map[shark.y][shark.x]].isdead = true;
    map[shark.y][shark.x] = 0;  
}

void dfs(vector<vector<int>> map, vector<Fish> fish, Shark shark) {
    eat_fish(map, fish, shark);
    
    for (int i = 1; i <= 16; i++) {
        if (fish[i].isdead)continue;
        int now_y = fish[i].y;
        int now_x = fish[i].x;
        int next_y, next_x;
        int now_dir = fish[i].dir;
        int next_dir;

        bool flag = false;
        for (int dir = now_dir; dir < now_dir + 8; dir++) {
            next_dir = dir % 8;
            next_y = now_y+dy[next_dir];
            next_x = now_x + dx[next_dir];
            //이동불가능하다면 45도 반시계 회전
            if (next_y<0 || next_x<0 || next_y>=N || next_x>=N || (next_y == shark.y && next_x == shark.x))continue;
            //현재방향으로 이동 가능하다면 이동
            int temp = map[next_y][next_x];
            fish[temp].y = now_y;
            fish[temp].x = now_x;
            fish[i].y = next_y;
            fish[i].x = next_x;
            fish[i].dir = next_dir;

            map[next_y][next_x] = map[now_y][now_x];
            map[now_y][now_x]=temp;
            break;
        }
    }
    move_shark(map, fish, shark);
}

void move_shark(vector<vector<int>> map, vector<Fish> fish, Shark shark) {
    int next_y = shark.y;
    int next_x=shark.x;

    bool flag = false;
    while (1) {
        shark.y+= dy[shark.dir];
        shark.x += dx[shark.dir];
        if (shark.y<0 || shark.x<0 || shark.y>=N || shark.x>=N)break;
        if (map[shark.y][shark.x]==0)continue;//해당위치의 물고기가 없다면 pass
        flag = true;
        dfs(map, fish, shark);
    }
    if (!flag) {//이동이 불가능하다면 최대값 갱신 후 빠져나옴 
        if (ans < shark.cnt)
            ans = shark.cnt;
    }
}

int main() {
    vector<Fish> fish(17);
    vector<vector<int>> map(4,vector<int>(4));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int dir;
            cin >> map[i][j];
            cin >> dir;
            fish[map[i][j]] = Fish({i,j,dir-1});
        }
    }
    Shark shark = Shark({ 0,0,0,0 });

    dfs(map, fish, shark);
    cout << ans;

    return 0;
}