백준 19236 청소년 상어 C++

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

19236번: 청소년 상어

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ19236.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ19236_1
//
//  Created by Hwayeon on 2021/10/22.
//

#include <iostream>
#include <string.h>
using namespace std;

struct Shark{
    int x;
    int y;
    int d;
    int eat = 0;
};
struct Fish{
    int x;
    int y;
    int num = 0;
    int d;
    bool arrive = true;
};
Fish fish;
Shark shark;

Fish fishes[17];

int area[4][4];

int dx[9] = {0, -1, -1, 0, 1 ,1, 1,  0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

int max_eat = 0;

void hunt(Shark now_shark, int area[][4], Fish fishes[17]){
    if(now_shark.eat > max_eat) max_eat = now_shark.eat;
    //1. 시뮬레이션 할 copy_area, copy_fishes 초기화
    Fish copy_fishes[17];
    int copy_area[4][4];
    memcpy(copy_area, area, sizeof(copy_area));
    memcpy(copy_fishes, fishes, sizeof(copy_fishes));
    
    //2. 물고기 이동
    for(int i=1; i<17; i++){
        //죽은 물고기
        if(!copy_fishes[i].arrive) continue;
        for(int d=copy_fishes[i].d; d<copy_fishes[i].d+8; d++){
            int nx, ny, nd;
            if(d <= 8) nd = d;
            else nd = d-8;
            nx = copy_fishes[i].x + dx[nd];
            ny = copy_fishes[i].y + dy[nd];
            if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
            if(nx == now_shark.x && ny == now_shark.y) continue;
            //빈칸 있는 곳으로 이동
            if(copy_area[nx][ny] == 0){
                copy_area[nx][ny] = i;
                copy_area[copy_fishes[i].x][copy_fishes[i].y] = 0;
                copy_fishes[i].d = nd;
                copy_fishes[i].x = nx;
                copy_fishes[i].y = ny;
            }
            //물고기 위치 바꾸기
            else{
                int swap = copy_area[nx][ny];
                copy_area[nx][ny] = i;
                copy_area[copy_fishes[i].x][copy_fishes[i].y] = swap;
                copy_fishes[swap].x = copy_fishes[i].x;
                copy_fishes[swap].y = copy_fishes[i].y;
                copy_fishes[i].d = nd;
                copy_fishes[i].x = nx;
                copy_fishes[i].y = ny;
            }
            break;
        }
    }
    
    //2. 상어 이동
    for(int dis=1; dis<4; dis++){
        int nx = now_shark.x + (dis*dx[now_shark.d]);
        int ny = now_shark.y + (dis*dy[now_shark.d]);
        if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
        if(copy_area[nx][ny] == 0) continue;
        //물고기 먹는다
        int eat_fish = copy_area[nx][ny];
        shark = now_shark;
        shark.eat += eat_fish;
        shark.d = copy_fishes[eat_fish].d;
        shark.x = nx;
        shark.y = ny;
        copy_fishes[eat_fish].arrive = false;
        copy_area[nx][ny] = 0;
        hunt(shark, copy_area, copy_fishes);
        copy_fishes[eat_fish].arrive = true;
        copy_area[nx][ny] = eat_fish;
    }
}

int main(int argc, const char * argv[]) {
    for(int x=0; x<4; x++){
        for(int y=0; y<4; y++){
            cin >> fish.num >> fish.d;
            fish.arrive = true;
            fish.x = x;
            fish.y = y;
            area[x][y] = fish.num;
            fishes[fish.num] = fish;
        }
    }
    //맨 처음 상어 (0, 0) 물고기를 먹는다
    fishes[area[0][0]].arrive = false;
    shark.eat = area[0][0];
    shark.d = fishes[area[0][0]].d;
    shark.x = 0;
    shark.y = 0;
    area[0][0] = 0;
    hunt(shark, area, fishes);
    cout << max_eat << endl;
    return 0;
}

---

풀이 과정

#include <iostream>
#include <string.h>
using namespace std;

struct Shark{
	//위치
    int x;
    int y;
    //방향
    int d;
    //먹은 물고기 번호의 합
    int eat = 0;
};
struct Fish{
	//위치
    int x;
    int y;
    //물고기 번호
    int num = 0;
    //방향
    int d;
    //arrive = true -> 살아 있음, arrive = false -> 죽었음
    bool arrive = true;
};
Fish fish;
Shark shark;

//fishes[i] = i번 상어의 정보
Fish fishes[17];
//area[x][y] = (x, y)에 있는 물고기 번호 (물고기가 없으면 area[x][y] = 0)
int area[4][4];

int dx[9] = {0, -1, -1, 0, 1 ,1, 1,  0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

int max_eat = 0;

void hunt(Shark now_shark, int area[][4], Fish fishes[17]){
	//현재까지 상어가 잡아먹은 물고기 번호의 합이 가장 최대인 경우, max_eat을 갱신한다
    if(now_shark.eat > max_eat) max_eat = now_shark.eat;
    
    //1. 시뮬레이션 할 copy_area, copy_fishes 초기화
    //물고기가 이동하고 상어가 물고기를 잡아먹으면, 이전 상태 값이 달라지므로 copy한 배열에서 시뮬레이션을 진행한다
    Fish copy_fishes[17];
    int copy_area[4][4];
    memcpy(copy_area, area, sizeof(copy_area));
    memcpy(copy_fishes, fishes, sizeof(copy_fishes));
    
    //2. 물고기 이동
    for(int i=1; i<17; i++){
        //죽은 물고기인 경우, 무시한다
        if(!copy_fishes[i].arrive) continue;
        
        //반시계 방향으로 방향 전환하면서 이동할 위치를 찾는다
        for(int d=copy_fishes[i].d; d<copy_fishes[i].d+8; d++){
            int nx, ny, nd;
            if(d <= 8) nd = d;
            else nd = d-8;
            nx = copy_fishes[i].x + dx[nd];
            ny = copy_fishes[i].y + dy[nd];
            
            //해당 위치가 격자를 벗어나는 경우, 해당 방향으로 물고기가 이동할 수 없다
            if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
            //해당 위치에 상어가 있는 경우, 해당 방향으로 물고기가 이동할 수 없다
            if(nx == now_shark.x && ny == now_shark.y) continue;
            
            //물고기가 이동할 방향을 찾은 경우,
            //빈칸 있는 곳으로 이동하는 경우,
            if(copy_area[nx][ny] == 0){
            	//이동할 칸에 물고기를 이동시키고, 이전에 있었던 칸은 빈칸으로 바꿔준다
                copy_area[nx][ny] = i;
                copy_area[copy_fishes[i].x][copy_fishes[i].y] = 0;
                //물고기의 새로운 방향, 위치를 저장한다
                copy_fishes[i].d = nd;
                copy_fishes[i].x = nx;
                copy_fishes[i].y = ny;
            }
            //다른 물고기가 있는 곳으로 이동하는 경우, 물고기 위치를 서로 바꾼다
            else{
                int swap = copy_area[nx][ny];
                copy_area[nx][ny] = i;
                copy_area[copy_fishes[i].x][copy_fishes[i].y] = swap;
                copy_fishes[swap].x = copy_fishes[i].x;
                copy_fishes[swap].y = copy_fishes[i].y;
                copy_fishes[i].d = nd;
                copy_fishes[i].x = nx;
                copy_fishes[i].y = ny;
            }
            break;
        }
    }
    
    //2. 상어 이동
    //상어의 방향으로 최대 3칸 이동 가능하다(격자에서 벗어날 수 없기 때문에)
    for(int dis=1; dis<4; dis++){
        int nx = now_shark.x + (dis*dx[now_shark.d]);
        int ny = now_shark.y + (dis*dy[now_shark.d]);
        
        //격자 밖으로 이동할 수 없다
        if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
        //물고기가 없는 칸으로 이동할 수 없다
        if(copy_area[nx][ny] == 0) continue;
        
        //물고기가 있는 칸인 경우, 상어를 이동시키고 물고기를 먹는다
        int eat_fish = copy_area[nx][ny];
        shark = now_shark;
        shark.eat += eat_fish;
        shark.d = copy_fishes[eat_fish].d;
        shark.x = nx;
        shark.y = ny;
        copy_fishes[eat_fish].arrive = false;
        copy_area[nx][ny] = 0;
        hunt(shark, copy_area, copy_fishes);
        //백트래킹을 위해 물고기와 공간 상태를 되돌린다
        copy_fishes[eat_fish].arrive = true;
        copy_area[nx][ny] = eat_fish;
    }
}

int main(int argc, const char * argv[]) {
    for(int x=0; x<4; x++){
        for(int y=0; y<4; y++){
            cin >> fish.num >> fish.d;
            fish.arrive = true;
            fish.x = x;
            fish.y = y;
            area[x][y] = fish.num;
            fishes[fish.num] = fish;
        }
    }
    
    //맨 처음 상어 (0, 0) 물고기를 먹는다
    fishes[area[0][0]].arrive = false;
    shark.eat = area[0][0];
    //상어의 방향을 잡아먹은 물고기의 방향으로 설정한다
    shark.d = fishes[area[0][0]].d;
    shark.x = 0;
    shark.y = 0;
    area[0][0] = 0;
    
    //물고기 사냥하기
    hunt(shark, area, fishes);
    cout << max_eat << endl;
    return 0;
}