[BOJ] 19236.청소년 상어(시뮬레이션, 백트래킹).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

조건이 많아서 복잡했던 문제다..

복잡한 만큼 디버깅도 힘들고 동작대로 차근차근 풀어나가는게 중요할 것 같다.

문제를 요약하고 풀었음에도 중간에 꼬여서 고생좀 했다...하핳..

조건들을 잘 살펴보자.

*. 물고기에 대한 조건

각 물고기는 번호와 방향을 가지고 있다

번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수

두 물고기가 같은 번호를 갖는 경우는 없다.

방향은 8가지 방향(상하좌우, 대각선) 중 하나

*. 청소년 상어에 대한 조건

청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 

상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동

*. 물고기 이동에 대한 조건

물고기는 번호가 작은 물고기부터 순서대로 이동

물고기는 한 칸을 이동

이동할 수 있는 칸은 빈 칸, 다른 물고기가 있는 칸,

물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동

이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸

각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전

만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다

외의 경우에는 그 칸으로 이동

*. 상어 이동에 대한 조건

물고기의 이동이 모두 끝나면 상어가 이동

상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다

상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 

이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.

물고기가 없는 칸으로는 이동할 수 없다.

상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.

시뮬레이션이 모두 그렇듯,

조건대로만 잘 구현하면 된다.

그렇다 말은 쉽다... ... ..

여기서 중요한 포인트는

재귀함수를 호출하는 단계에서 원본 데이터를 보존하기 위해

배열, 객체를 복사 후 사용해야 한다는 점이다.

배열, 객체는 힙에 생성된 메모리를 가리키는 포인터를 저장하고 있으므로

매개변수로 계속 다른 데이터가 넘어오는 것 같아도

static 으로 사용하는 것처럼 원본 데이터는 계속 값이 변하게 된다.

(하나의 배열, 객체를 계속 변경하면서 사용하는 듯한..)

그래서 매개변수로 들어온 초기 배열, 객체를 복사해서 사용하여 다음 재귀함수 호출 시 넘겨줘야 한다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ19236 {
 
    static int N = 4, res;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static class Fish {
        int x, y, dir;
 
        public Fish(int x, int y, int dir) {
            super();
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int[][] map = new int[N][N];
        Fish[] fishes = new Fish[17];
        // 공간 정보 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int a = Integer.parseInt(st.nextToken()); // 물고기 번호
                int b = Integer.parseInt(st.nextToken()) - 1; // 방향
                
                // map에는 물고기 번호를 저장
                map[i][j] = a;
                // 해당 번호의 물고기의 위치와 방향 저장
                fishes[a] = new Fish(i, j, b);
            }
        }
        
        // 먼저 상어가 (0,0)공간에 들어간다.
        // (0,0)에 있는 물고기를 먹고
        res = map[0][0];
        // 상어의 방향은 (0, 0)에 있던 물고기의 방향을 갖는다.
        Fish shark = new Fish(0, 0, fishes[map[0][0]].dir);
        // 먹힌 고기는 정보를 지워주자
        fishes[map[0][0]] = null;
        // 상어를 map에 위치시켜주자. (상어는 -1 번)
        map[0][0] = -1;
        
        // map, shark, fishes 데이터는 계속 변하므로 매개변수로 들고 다니자.
        process(map, shark, fishes, res);
        
        System.out.println(res);
        
    }
 
    private static void process(int[][] map, Fish shark, Fish[] fishes, int sum) {
        
        /*
         * 원본 데이터를 유지하기 위해 map, shark, fishes 를 복사해서 사용.
         */
        // map 복사
        int[][] tmpMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tmpMap[i][j] = map[i][j]; 
            }
        }
        // shark 복사
        Fish tmpShark = new Fish(shark.x, shark.y, shark.dir);
        // fishes 복사
        Fish[] tmpFishes = new Fish[17];
        for (int i = 1; i <= 16; i++) {
            if(fishes[i] == null) continue;
            tmpFishes[i] = new Fish(fishes[i].x, fishes[i].y, fishes[i].dir);
        } 
        
        /*
         * 먼저 물고기가 이동
         */
        for (int f = 1; f <= 16; f++) {
            
            // i번 물고기의 정보
            Fish now = tmpFishes[f];
            // 먹힌 물고기면 pass
            if(now == null) continue;
                        
            // 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전
            int origDir = now.dir;
            do {
                // 물고기는 한 칸을 이동
                int xx = now.x + dx[now.dir];
                int yy = now.y + dy[now.dir];
                
                // 상어가 있거나, 공간을 넘어가면 회전
                if(xx < 0 || xx >= N || yy < 0 || yy >= N || tmpMap[xx][yy] == -1) {
                    now.dir = (now.dir + 1) % 8;
                    continue;
                }
                
                // 빈 칸 or 다른 물고기가 있는 칸이라면 이동하고 위치를 바꿔주자
                // 이동할 위치의 물고기 정보 저장
                Fish ftmp = tmpFishes[tmpMap[xx][yy]]; 
                if(ftmp == null) { // 이동할 위치에 물고기가 없다면
                    // 내 위치만 갱신
                    tmpFishes[f] = new Fish(xx, yy, now.dir);
                }
                else { // 이동할 위치에 물고기가 있다면
                    // 내 위치와 이동할 위치의 정보를 교환
                    tmpFishes[tmpMap[xx][yy]] = new Fish(now.x, now.y, ftmp.dir);
                    tmpFishes[f] = new Fish(xx, yy, now.dir);
                }
                
                // 물고기 정보도 교환
                int ntmp = tmpMap[xx][yy];
                tmpMap[xx][yy] = f;
                tmpMap[now.x][now.y] = ntmp;
                
                break;
                
            } while (now.dir != origDir); // 처음 방향으로 돌아올 때까지
        }// 이동할 수 있는 칸이 없으면 이동을 하지 않는다
        
        /*
         * 상어가 이동
         */
        // 이동할 수 있을 때까지 다 이동해보자(최대 3칸)
        for (int d = 1; d <= 3; d++) {
            int xx = tmpShark.x + dx[tmpShark.dir] * d;
            int yy = tmpShark.y + dy[tmpShark.dir] * d;
            
            // 범위 넘어가면 pass
            if(xx < 0 || xx >= N || yy < 0 || yy >= N) break;
            // 물고기가 없는 칸일 경우 pass
            if(tmpMap[xx][yy] == 0) continue;
            
            // 상어가 물고기가 있는 칸으로 이동했다면
            // 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.
            int eatNum = tmpMap[xx][yy]; // 이동할 위치의 물고기 번호
            Fish fish = tmpFishes[tmpMap[xx][yy]]; // 이동할 위치의 물고기 정보
            
            // 먹힌 물고기 정보에서 삭제
            tmpFishes[tmpMap[xx][yy]] = null;
            // 상어 정보 갱신
            tmpShark = new Fish(fish.x, fish.y, fish.dir);
            // map 갱신
            tmpMap[xx][yy] = -1;
            // 원래 상어가 있던 위치는 비우자
            tmpMap[shark.x][shark.y] = 0;
            
            // 수정된 tmp 데이터를 전송(원본 데이터는 보존)
            process(tmpMap, tmpShark, tmpFishes, sum + eatNum);
            
            /*
             * 백트래킹
             */
    
            // 초기 상어 위치로 되돌리기
            tmpMap[shark.x][shark.y] = -1;
            // 먹힌 물고기를 되돌리기
            tmpMap[xx][yy] = eatNum;
            // 초기 상어 정보 되돌리기
            tmpShark = new Fish(shark.x, shark.y, shark.dir);
            // 먹힌 물고기 정보 되돌리기
            tmpFishes[tmpMap[xx][yy]] = new Fish(fish.x, fish.y, fish.dir);
        } // 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.
        
        // 결과 갱신
        res = Math.max(res, sum);
    }
 
}