[백준 19236번] 청소년 상어

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

19236번: 청소년 상어

<문제 풀이> 백 트랙킹

이 문제는 백트래킹을 할 때 상태 정보 백업 및 복원이 가장 핵심입니다.

상어를 1칸 이동, 2칸 이동, 3칸 이동시키고 각각에 대해서 재귀 호출할 때 재귀 호출 전에 백업, 호출 후 복원을 하면 되고, 물고기들이 이동하는 건 클래스로 좌표와 방향을 저장해 두고 1번부터 16번까지 단순히 움직이면 됩니다.

 

이때 주의할 점은 상어는 물고기가 있는 칸만 이동할 수 있습니다.
(2칸에 물고기가 없다고 끝내면 안 되고 3칸도 이동해 보아야 한다.)

 

 

 

<C++ 소스 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
#define SHARK -1
#define EMPTY -2
class pos {
public:
    int x, y, dir;
    void rotate() {
        dir++;
        if (dir == 9) dir = 1;
 
    }
    void del() {
        x = -1; y = -1; dir = -1;
    }
    bool exist() {
        if (x == -1 && y == -1 && dir == -1) return false;
        else return true;
    }
};
 
const int dx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
 
pos info[17]; //1~16번 좌표 방향 정보
int board[4][4];
pos shark; //현재 상어 상태
int res = 0;
void move() {
    for (int i = 1; i <= 16; i++) {
        if (!info[i].exist()) continue;
        int startDir = info[i].dir;
        while (true) {
            int nx = info[i].x + dx[info[i].dir];
            int ny = info[i].y + dy[info[i].dir];
            int next = board[nx][ny];
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || board[nx][ny] == SHARK) {
                info[i].rotate();
                if (startDir == info[i].dir)break;
                continue;
            }
            if (board[nx][ny] == EMPTY) {
                board[nx][ny] = i;
                board[info[i].x][info[i].y] = EMPTY;
                info[i].x = nx;
                info[i].y = ny;
            }
            else {
                swap(board[info[i].x][info[i].y], board[nx][ny]);
                swap(info[i], info[next]);
                swap(info[i].dir, info[next].dir);
            }
            break;
        }
    }
}
 
/*백트랙킹 상태 정보 백업용*/
void backupBoard(int des[4][4], int src[4][4]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            des[i][j] = src[i][j];
        }
    }
}
void backupInfo(pos des[17], pos src[17]) {
    for (int i = 0; i < 17; i++) {
        des[i] = src[i];
    }
}
 
 
void solve(int sum) {
    move();
    int cx = shark.x;
    int cy = shark.y;
    int dir = shark.dir;
 
    for (int k = 1; k <= 3; k++) {
        int nx = cx + dx[dir] * k;
        int ny = cy + dy[dir] * k;
        if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) return;
        if (board[nx][ny] == EMPTY) continue;
        int tempBoard[4][4];
        pos tempInfo[17];
        backupBoard(tempBoard, board);
        backupInfo(tempInfo, info);
        shark.x = nx;
        shark.y = ny;
        int num = board[nx][ny];
        res = max(res, sum + num);
        shark.dir = info[num].dir;
        board[nx][ny] = SHARK;
        board[cx][cy] = EMPTY;
        info[num].del();
 
        solve(sum + num);
        
        shark.x = cx;
        shark.y = cy;
        shark.dir = dir;
        backupBoard(board, tempBoard);
        backupInfo(info, tempInfo);
    }    
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int a, b;
            cin >> a >> b;
            info[a].dir = b;
            info[a].x = i;
            info[a].y = j;
            board[i][j] = a;
        }
    }
 
    shark.x = 0;
    shark.y = 0;
    shark.dir = info[board[0][0]].dir;
 
    info[board[0][0]].del();
    int num  = board[0][0];
    board[0][0] = SHARK;
    solve(num);
    cout << res;
    
    return 0;
}