boj 19236 청소년 상어

www.acmicpc.net/problem/19236

19236번: 청소년 상어

이 문제는 고려해야할 부분이 많습니다.

 

상어와 물고기는 8방향 이동을 할 수 있습니다.

순서는 (1)상어가 물고기를 먹고 (2)물고기들이 이동합니다.

상어가 처음에는 (0, 0)에 있는 물고기를 먹으며 먹은 물고기의 방향을 갖게되고, 이후에는 주어진 방향으로만 이동합니다.

 

상어는 한 번에 여러 칸을 이동할 수 있고, 물고기가 있는 칸으로만 이동할 수 있습니다.

따라서 이동경로에 있는 물고기 후보 중 하나를 골라 먹습니다.

 

물고기는 맵 밖이나 상어가 있는 칸으로 이동할 수 없으며 이동할 때 번호가 작은 물고기부터 순서대로 이동합니다. (1번 ~ 16번)

(만약, 해당 번호의 물고기가 먹힌상태면 다음 번호가 이동하면 됩니다.)

물고기는 주어진 방향으로만 1칸 이동하며, 그 칸에 물고기가 있으면 서로의 자리를 바꿉니다.

만약 물고기가 이동할 수 없는 경우에는 이동할 수 있을 때까지 방향을 45도 반시계 방향으로 회전한 후 이동합니다.

 

 

이제 제 로직을 설명하겠습니다.

 

저는 입력을 받으면서 (0, 0)에 상어를 미리 놓고, (1)물고기들 이동, (2)상어 이동 순서대로 구현하였습니다.

func함수의 파라미터에 (현재 배열의 상태(arr), 물고기의 상태(f), 상어의 좌표(X, Y), 상어의 방향(D), 현재 먹은 물고기들의 번호합(S))

을 넘겨주는 재귀함수로 구성하였습니다.

 

함수가 돌 때마다 최대 합을 갱신해주었고, 물고기 이동부터 시작합니다.

먹히지 않은 물고기들만 이동하는 방식이며, 물고기가 이동할 수 있을 때까지 방향을 45도씩 반시계방향으로 회전시키며 반복문을 돌렸습니다.

물고기가 이동하고나면 break를 합니다.

 

이제 상어가 이동합니다.

상어는 한 방향으로만 움직일 수 있지만 여러 칸 이동이 가능하므로 맵 밖으로 나갈 때까지 반복문을 돌려줍니다.

물고기가 없는 칸은 갈 수 없으므로 continue를 하였고, 물고기가 있는 칸은 먹은 후의 상태를 다음 재귀로 넘겨주었습니다. (이는 백트래킹으로 구현하였습니다.)

 

상어와 물고기의 모든 이동이 끝나면 계속 갱신해주었던 답을 출력해줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int x, y, d;
 
        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
    static boolean eat[] = new boolean[17];
    static int ans;
 
    static void func(int[][] arr, Pair[] f, int X, int Y, int D, int S) {
        ans = Math.max(ans, S);
        for (int i = 1; i <= 16; i++) {
            if (eat[i])
                continue;
 
            int x = f[i].x;
            int y = f[i].y;
 
            int nx = x;
            int ny = y;
 
            while (true) {
                nx = x + direct[f[i].d][0];
                ny = y + direct[f[i].d][1];
 
                if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
                if (arr[nx][ny] == -1) {
                    f[i].d = (f[i].d + 1) % 8;
                    continue;
                }
 
                if (arr[nx][ny] == 0) {
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[nx][ny] = arr[x][y];
                    arr[x][y] = 0;
                } else {
                    int tmp = arr[x][y];
                    f[arr[nx][ny]].x = x;
                    f[arr[nx][ny]].y = y;
                    f[i].x = nx;
                    f[i].y = ny;
                    arr[x][y] = arr[nx][ny];
                    arr[nx][ny] = tmp;
                }
                break;
            }
        }
 
        int nx = X;
        int ny = Y;
        while (true) {
            nx = nx + direct[D][0];
            ny = ny + direct[D][1];
 
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
                break;
            if (arr[nx][ny] == 0)
                continue;
 
            int tmp = arr[nx][ny];
            arr[nx][ny] = -1;
            arr[X][Y] = 0;
            eat[tmp] = true;
            int arr2[][] = new int[4][4];
            for (int i = 0; i < 4; i++)
                arr2[i] = arr[i].clone();
            Pair f2[] = new Pair[17];
            for (int i = 1; i <= 16; i++)
                f2[i] = new Pair(f[i].x, f[i].y, f[i].d);
            func(arr2, f2, nx, ny, f[tmp].d, S + tmp);
            eat[tmp] = false;
            arr[nx][ny] = tmp;
            arr[X][Y] = -1;
        }
    }
 
    public static void main(String[] args) throws Exception {
        int list[][] = new int[4][4];
        Pair fish[] = new Pair[17];
 
        int nowx = 0, nowy = 0, nowd = 0, sum = 0;
        int x, d;
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
 
                x = Integer.parseInt(st.nextToken());
                d = Integer.parseInt(st.nextToken()) - 1;
 
                list[i][j] = x;
                fish[x] = new Pair(i, j, d);
                if (i == 0 && j == 0) {
                    list[i][j] = -1;
                    eat[x] = true;
                    nowx = i;
                    nowy = j;
                    nowd = d;
                    sum += x;
                }
            }
        }
        func(list, fish, nowx, nowy, nowd, sum);
        System.out.println(ans);
    }
}