백준 19236 - 청소년 상어

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

문제 요약

1. 4x4 공간이 주어지며 1~16 번호를 가진 물고기가 한칸에 하나씩 존재한다.

2. 각 물고기는 방향을 가지고 있으며, 1~16 순서대로 이동한다.

2-1. 물고기가 이동할 수 없다면(상어가 존재 or 범위를 벗어남) 이동할 수 있을때까지 반시계 회전한다.

2-2. 물고기가 이동하는 곳에 다른 물고기가 있다면 서로 위치를 바꾼다.

3. 상어는 처음에 (0,0)에 있는 물고기를 먹고 시작한다.

3-1. 상어는 빈 공간에 이동할 수 없으며, 물고기를 먹으면 물고기의 방향을 가진다.

 

위 과정을 반복하여 상어가 먹은 물고기의 번호를 더한 값의 최댓값을 구하는 것이 목표이다.

 

풀이 과정

해당 문제는 상어가 이동하는 곳이 정해져 있지 않으며 최댓값을 구해야 하기 때문에, DFS + 백트래킹을 사용하여 풀이하였다.

(백트래킹이란, 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다.)

 

1. 먼저 물고기의 좌표는 계속해서 변하기 때문에, 아래와 같이 구조체 덱을 하나 선언하였다.

각 물고기의 좌표와 방향을 저장한다.

typedef struct option {
    int y,x,dir;
}op;
deque < op > fishq; // fishq[1] ~ fishq[16] 까지 저장

 

 

2. 가장 먼저 상어는 (0,0) 위치에 있는 물고기를 먹기 때문에 해당 물고기의 좌표는 (-1,-1) 로 설정한다.

    // 0,0 좌표에 있는 물고기 먹음
    startFishNum = space[0][0];
    space[0][0] = -1;
    // 먹힌 물고기의 좌표 : -1,-1
    fishq[startFishNum].y = -1, fishq[startFishNum].x = -1;

 

3. 이제 DFS를 수행하는데, 파라미터로 (물고기 번호 합, 상어 y, 상어 x, 상어 방향) 을 넘겨준다.

DFS를 수행할 때 마다 최댓값을 계산해주며, 물고기를 전부 이동시킨 후 상어를 이동시킨다.

 

여기서 중요한 점은 이전 상태를 저장해줘야 하는 것인데, DFS가 수행되기 전에 임시 배열을 선언하고, 물고기와 상어의 이동하기 전 상태를 저장해준다.

임시 배열은 DFS 함수 내에서 지역배열로 선언해줘야 한다.

전역배열로 선언한다면 각 DFS 호출 간에 상태가 공유되므로 제대로 된 결과가 나오기 어렵다.

    // 물고기+상어 이동 전 상태 저장
    int temp[4][4];
    deque < op > tempq;
    copySpace(temp,space);
    for(int i=1; i<=16; i++) {
        tempq[i] = fishq[i];
    }
    
    
    ......
    
    
    // 공간 원복
    // 물고기+상어 이동 전 상태 저장
    copySpace(space,temp);
    for(int i=1; i<=16; i++) {
        fishq[i] = tempq[i];
    }

 

3-1. 이제 1~16까지의 물고기를 이동시켜 주고, 상어를 이동시켜야 한다.

상어는 물고기가 존재하는 여러 칸에 이동할 수 있으므로, 모든 경우의 수를 탐색해야 한다.

위 상황에서는 빨간색 네모 칸 3개로 이동하는 모든 경우의 수를 탐색해야 한다.

만약 1번으로 이동했다면 -> 상어는 다시 돌아와서 4번으로 이동해봐야 하고, -> 또 다시 돌아와서 12번으로도 이동해봐야 한다.

따라서 상어가 이동한 후 -> DFS를 실행시킨 다음 -> 다시 원래의 상태로 돌려놓아야 한다.

    while(1) {
        sNexty += dy[sDir], sNextx += dx[sDir];
        // 상어가 이동 불가능하다면 종료
        if(sNexty >= 4 || sNexty < 0 || sNextx >= 4 || sNextx < 0) {
            break;
        }
        if(space[sNexty][sNextx] == 0) continue;

        eatFishNum = space[sNexty][sNextx];
        sNextDir = fishq[eatFishNum].dir;

        changeSharkState(sy,sx,sNexty,sNextx,eatFishNum,true);
        solution(sum+eatFishNum,sNexty,sNextx,sNextDir);
        changeSharkState(sy,sx,sNexty,sNextx,eatFishNum,false);
    }

 

3-2. 상어가 더이상 이동 불가능하다면 원래 저장해놨던 상태를 원복 해야한다.

예를들어, DFS를 3번째 호출해서 상어가 이동을 마치고 공간을 원복하지 않았다고 가정해보자.

그렇다면 2번째 DFS호출로 돌아와서 상어가 다음 칸으로 이동해야 하는데, 원래 상어가 있던 공간이 아니라 3번째 DFS 호출에서 바꿔놓은 공간을 사용하게 되는 것이다.

 

 

전체 코드

#include <iostream>
#include <stdio.h>
#include <deque>
using namespace std;
// 2:57
int dy[8] = {-1,-1,0,1,1,1,0,-1};
int dx[8] = {0,-1,-1,-1,0,1,1,1};

// 물고기 좌표
typedef struct option {
    int y,x,dir;
}op;
deque < op > fishq;

// 공간  0:빈공간, -1:상어
int space[4][4];

int ans = -1;

void test() {
    printf("\n");
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            printf("%d ",space[i][j]);
        }
        printf("\n");
    }
}

void moveFish(int fishNum, int y, int x, int ny, int nx, int fdir) {
    int existFishNum = space[ny][nx];
    fishq[fishNum].y = ny, fishq[fishNum].x = nx;
    fishq[fishNum].dir = fdir;
    space[ny][nx] = fishNum;

    // 이동하는 칸이 빈공간
    if(space[ny][nx] == 0) {
        space[y][x] = 0;
    }
    // 이동하는 칸에 물고기 존재
    else {
        space[y][x] = existFishNum;
        fishq[existFishNum].y = y, fishq[existFishNum].x = x;
    }
}

// B를 A에 저장
void copySpace(int A[][4], int B[][4]) {
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            A[i][j] = B[i][j];
        }
    }
}

void changeSharkState(int y, int x, int ny, int nx, int fishNum, bool flag) {
    // 상어 이동함
    if(flag) {
        space[y][x] = 0;
        space[ny][nx] = -1;
        fishq[fishNum].y = -1, fishq[fishNum].x = -1;
    }
    // 상어 복귀
    else {
        space[y][x] = -1;
        space[ny][nx] = fishNum;
        fishq[fishNum].y = ny, fishq[fishNum].x = nx;
    }
}

void solution(int sum, int sy, int sx, int sDir) {
    ans = (ans < sum) ? sum : ans;

    // 물고기+상어 이동 전 상태 저장
    int temp[4][4];
    deque < op > tempq;
    copySpace(temp,space);
    for(int i=1; i<=16; i++) {
        tempq[i] = fishq[i];
    }

    int fy,fx,fdir;
    int nexty, nextx;
    // 물고기 전체 이동
    for(int i=1; i<=16; i++) {
        fy = fishq[i].y, fx = fishq[i].x, fdir = fishq[i].dir;
        if(fy == -1 && fx == -1) continue;
        
        nexty = fy, nextx = fx;
        // 물고기 이동
        while(1) {
            nexty = fy + dy[fdir], nextx = fx + dx[fdir];
            // 경계 밖 또는 상어 존재할 경우 반시계 회전
            if(nexty >= 4 || nexty < 0 || nextx >= 4 || nextx < 0 || space[nexty][nextx] == -1) {
                fdir = (fdir+1) % 8;
            }
            else {
                moveFish(i,fy,fx,nexty,nextx,fdir);
                break;
            }
        }
    }
    //test();

    // 상어 이동
    int sNexty = sy, sNextx = sx, sNextDir;
    int eatFishNum;
    while(1) {
        sNexty += dy[sDir], sNextx += dx[sDir];
        // 상어가 이동 불가능하다면 종료
        if(sNexty >= 4 || sNexty < 0 || sNextx >= 4 || sNextx < 0) {
            break;
        }
        if(space[sNexty][sNextx] == 0) continue;

        eatFishNum = space[sNexty][sNextx];
        sNextDir = fishq[eatFishNum].dir;

        changeSharkState(sy,sx,sNexty,sNextx,eatFishNum,true);
        solution(sum+eatFishNum,sNexty,sNextx,sNextDir);
        changeSharkState(sy,sx,sNexty,sNextx,eatFishNum,false);
    }

    // 공간 원복
    // 물고기+상어 이동 전 상태 저장
    copySpace(space,temp);
    for(int i=1; i<=16; i++) {
        fishq[i] = tempq[i];
    }
}

int main() {
    int a,b;
    int startFishNum;
    for(int i=0; i<4; i++) {
        for(int j=0; j<4; j++) {
            scanf("%d %d",&a,&b);
            fishq[a].dir = b-1;
            fishq[a].y = i;
            fishq[a].x = j;
            space[i][j] = a;
        }
    }
    // 0,0 좌표에 있는 물고기 먹음
    startFishNum = space[0][0];
    space[0][0] = -1;
    // 먹힌 물고기의 좌표 : -1,-1
    fishq[startFishNum].y = -1, fishq[startFishNum].x = -1;

    solution(startFishNum,0,0,fishq[startFishNum].dir);
    printf("%d\n",ans);
}