[백준 19236] 청소년 상어 (C++)

문제 링크: www.acmicpc.net/problem/19236

19236번: 청소년 상어

1. 주의할 점

- DFS를 통해 수행하므로, 갱신 + 원복을 잘 처리해야 한다

- 처리해야 하는 변수가 많아 헷갈릴 수 있으니 잘 정리하고 시작한다

 

2. 구현

- 8방향 탐색을 원활하게 처리하기 위해, 입력받을 때 각 물고기의 방향-1값을 저장한다

- 물고기의 정보를 Fish[]구조체에 담는다. 구조체는 행, 열, 진행방향으로 구성되어있다

- 현재 물고기의 위치는 Arr[][] 배열에 저장한다

- 물고기에 대한 정보를 입력 받은 이후, (0,0)에 위치한 물고기를 죽이고 상어로 표시하고 DFS()를 시작한다

- DFS()의 매개변수는 상어의 y,x,dir값과 현재까지 상어가 먹은 물고기 번호의 합으로 구성되어있다

- 원복을 하기 위해 Dup[][]과 Fdup[]에 Arr[][]와 Fish[]에 대한 정보를 복사한다

- 물고기의 진행을 move_fish() 함수를 통해 수행한다

- 이후, 상어의 움직임을 시작하며 물고기를 잡아 먹을 수 있는 경우, [물고기 죽임 + 상어 위치전환]을 처리하고 DFS()를 호출한다

- DFS() 호출이 끝나면, 수행했던 [물고기 죽임 + 상어 위치전환]을 원복한다

- 상어의 움직임이 끝나면, 모든 정보를 원복한다(Arr[][], Fish[])

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
struct info{
    int x,y,dir;        //dir=-1: 죽은 물고기
};
info tmp;
int dx[8]={0,-1,-1,-1,0,1,1,1};
int dy[8]={-1,-1,0,1,1,1,0,-1};
info fish[17];
int result=0;
int arr[4][4];      //1~16: 물고기, 0: Shark, -1: 죽은 물고기

void move_fish(){
    for(int i=1;i<17;i++){
        int cx = fish[i].x;
        int cy = fish[i].y;
        int cd = fish[i].dir;
        if(cd==-1) continue;       //죽은 물고기
        int nx,ny;
        int nd = cd;
        for(int j=0;j<8;j++){
            nx = cx+dx[nd];
            ny = cy+dy[nd];
            if(nx>=0 && ny>=0 && nx<4 && ny<4){
                int idx = arr[ny][nx];
                if(idx==0){     //shark
                    nd = (nd+1)%8;
                    continue;
                }
                //물고기 자리 교환
                arr[ny][nx] = i;
                fish[i].x = nx;
                fish[i].y = ny;
                fish[i].dir = nd;
                
                arr[cy][cx] = idx;
                fish[idx].x = cx;
                fish[idx].y = cy;
                break;
            }
            nd = (nd+1)%8;
        }
    }
}

void dfs(int y, int x, int dir, int sum){
    info fdup[17];
    int dup[4][4];
    //복사
    for(int i=1;i<17;i++)
        fdup[i] = fish[i];
    memcpy(dup,arr,sizeof(dup));
    
    //물고기 이동
    move_fish();
    
    //상어 이동
    int nx = x;
    int ny = y;
    while(1){
        nx+=dx[dir];
        ny+=dy[dir];
        if(nx>=0 && ny>=0 && nx<4 && ny<4){
            int idx = arr[ny][nx];
            if(idx==-1)   continue;     //물고기가 없어서 이동 불가
            //물고기
            int fd = fish[idx].dir;
            //죽임 처리 + 상어 자리이동
            fish[idx].dir = -1;
            arr[y][x] = -1;
            arr[ny][nx] = 0;
            dfs(ny,nx,fd,sum+idx);
            //원복
            fish[idx].dir = fd;
            arr[y][x] = 0;
            arr[ny][nx] = idx;
        }
        else break;
    }
    result = max(result,sum);
    
    //원복
    memcpy(arr,dup,sizeof(dup));
    for(int i=1;i<17;i++)
        fish[i] = fdup[i];
    return;
}

int main() {
    int a, b,val;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++){
            cin>>a>>b;
            arr[i][j]=a;
            fish[a].x=j;
            fish[a].y=i;
            fish[a].dir=b-1;
        }
    val = arr[0][0];
    int sd = fish[val].dir;
    fish[val].dir=-1;
    arr[0][0]=0;
    dfs(0,0,sd,val);   
    cout<<result;
    return 0;
}