[DFS 백트래킹] 백준 19236 청소년 상어 C++

※ 문제

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

19236번: 청소년 상어

※ 풀이

1) 상어와 물고기의 x좌표, y좌표, 방향을 저장할 구조체를 선언하고, 물고기 번호를 저장할 공간 배열, 그리고 물고기 번호별로 x좌표, y좌표, 방향을 저장할 물고기 배열을 따로 선언했다.

그 이유는 물고기를 작은 번호 순대로 이동시켜야 하는데, 공간 배열에 물고기 번호를 저장하면 좌표를 이용해 물고기 번호는 찾을 수 있으나, 물고기 번호를 이용해 물고기 좌표를 찾을 수 없기 때문이다.

 

2) 상어 첫 위치는 (0,0)에서 시작하나, 편의상 (1,1)에서 시작하였다.

 

3) 물고기 이동한 후 공간 배열 및 물고기 배열을 업데이트하고, 상어가 향한 방향으로 갈 수 있는 위치에서 먹이를 먹는다. 해당 방향으로 상어가 갈 수 있는 위치는 배열이 4X4밖에 되지 않아서 최대 3번만 확인하면 된다.

 

4) 3)의 과정을 DFS로 반복해 더이상 이동할 수 없을 때까지(물고기가 없거나, 벽 끝) 반복한다. 또한, 가지 치기가 끝날 때마다 최대 번호 합을 저장하고, 백트래킹을 이용해 가지치기를 하며 구한 최대 번호 합과 공간 배열과 물고기 배열을 원래대로 바꿔야 한다.

 

* 백트래킹을 위한 원래 배열들을 어디서 저장해야 하는지 고민했는데, 물고기 이동을 끝낸 후 배열들을 임시 변수에 저장해놓으면 된다. 

* update 함수를 따로 사용하려 했으나 배열 전달이 복잡해져 dfs 함수 하나에 물고기 이동과 상어 위치 업데이트 하는 코드를 모두 작성하였다.

#include<iostream>

using namespace std;

struct pos {
    int x, y, d; // 상어 및 물고기 위치 및 방향
};

int ans;
int board[6][6]; // 공간 상태
pos fish[17]; // 몰고기 위치 및 방향
int dx[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 }; // 반시계 방향 상하좌우, 대각선
int dy[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

void dfs(pos shark, int val) {
    // 물고기 이동 update
    for (int i = 1; i <= 16; i++) {
        int dir = fish[i].d;
        if (dir == 0) continue; // 해당 번호 물고기 없는 경우

        int newX = fish[i].x + dx[dir];
        int newY = fish[i].y + dy[dir];
		
        // 물고기가 이동할 수 없는 경우, 반시계 45도 회전
        while (((newX == 0) || (newY == 0) || (newX > 4) || (newY > 4)) || ((shark.x == newX) && (shark.y == newY))) {
            dir += 1;
            dir %= 9;
            if (dir == 0) dir += 1;
            newX = fish[i].x + dx[dir];
            newY = fish[i].y + dy[dir];
        }
		
        // 물고기 번호 swap
        int temp = board[newY][newX];
        board[newY][newX] = i;
        board[fish[i].y][fish[i].x] = temp;
		
        // 물고기 위치 swap
        fish[temp].x = fish[i].x;
        fish[temp].y = fish[i].y;

        fish[i].x = newX;
        fish[i].y = newY;
        fish[i].d = dir;
    }

    // 물고기 이동 후 상태 저장
    int orgBoard[6][6];
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            orgBoard[i][j] = board[i][j];
        }
    }
    pos orgFish[17];
    for (int j = 1; j <= 16; j++) {
        orgFish[j] = fish[j];
    }
	
    // 상어가 갈 수 있는 위치 확인
    int x = shark.x;
    int y = shark.y;
    for (int i = 0; i < 3; i++) {
        x += dx[shark.d];
        y += dy[shark.d];
		
        // 상어가 더이상 이동할 수 없는 경우
        int temp = board[y][x];
        if ((x == 0) || (y == 0) || (x > 4) || (y > 4)) {
            ans = max(val, ans);
            break;
        }
        if (temp == 0) {
            ans = max(val, ans);
            continue;
        }

        // 상어 위치를 상어가 먹은 먹이 위치로 바꾸기
        pos newShark = { x, y, fish[temp].d };
        val += temp; 
        board[y][x] = 0;
        fish[temp].d = 0;

        dfs(newShark, val);

        // 백트래킹(공간 및 인덱스 배열 원래대로)
        val -= temp;
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                board[j][k] = orgBoard[j][k];
            }
        }
        for (int j = 1; j <= 16; j++) {
            fish[j] = orgFish[j];
        }
    }
}

int main()
{
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            cin >> board[i][j]; // 공간 상태(위치->물고기 번호)
            cin >> fish[board[i][j]].d; // 물고기 번호->위치 및 방향
            
            fish[board[i][j]].x = j;
            fish[board[i][j]].y = i;
        }
    }

    // 상어 첫 먹이 및 위치 바꾸기
    int temp = board[1][1];
    pos shark = { 1, 1, fish[temp].d };
    fish[temp].d = 0;
    board[1][1] = 0;

    // dfs 실행
    dfs(shark, temp);

    cout << ans;
    
    return 0;
}