BOJ G2 19236 청소년 상어 JAVA

 

19236번: 청소년 상어

 

문제 읽기

문제를 읽으면서 다음과 같이 적어보았다. 기본은 시뮬레이션 문제이지만, dfs 개념도 필요한 문제이다.

0. 상어가 (0,0)에 들어옴(초기 상태 설정)

1. 물고기 작은 수부터 전부 한 칸씩 이동 (빈 칸 또는 물고기 칸만 가능. 45도 반 시계 회전.)
2. 상어 이동. 해당 방향대로 물고기가 있는 칸으로만 가능. (모든 경우의 수를 생각해서 dfs)

=> 상어의 이동 경로가 여러가지이기 때문에 반복문이 아닌 dfs로 수행하자.

그리고 물고기 작은 수부터 이동해야 하는데 map 형태에서는 뭐가 제일 작은 지 모르니까 
map에도 적되 따로 array로 위치 좌표를 빼놓자.

 

일단 위와 같이 생각하고 사용자 정의 class 두 개를 만들고 시작했다. 그린데 dfs에 생각보다 인자로 넘겨줘야 할 게 많았다.. 그리고 fish 배열의 class는 Pos인데 map 배열의 class는 Fish라서 처음에 좀 헷갈렸다. 다음부터는 class 이름 지을 떄도 잘 지어야겠다.

 

나머지 항목들은 구현을 하는 부분이 대부분이기 때문에 차분하게 구현하면 풀 수 있는 문제인 것 같다.

---

실수한 부분

사용자 정의 class 이차원 배열 복사

나는 이차원 배열을 복사할 때는 보통 다음과 같은 myClone 함수를 만들어 사용한다.

static private Object[][] myClone(Object[][] map){
	Object[][] cloneMap = new Object[R][C];
	for (int r = 0; r < R; r++){
		cloneMap[r] = map[r].clone();
	}
	return cloneMap;
}

위 코드는 언뜻 보면 괜찮을 것 같지만 문제가 있다.

Object가 int나 String 같은 타입이면 괜찮지만, 직접 만든 사용자 정의 클래스이면 문제가 될 수 있다. 그렇다면 문제가 되는 이유가 뭘까? clone()이라는 함수에서 뭔가 문제가 생기는 걸까?

 

그러면 다음과 같이 코드를 바꾸면 어떨까

static private Object[][] myClone(Object[][] map){
	Object[][] cloneMap = new Object[R][C];
	for (int r = 0; r < R; r++){
		for (int c = 0; c < c; c++){
			cloneMap[r][c] = map[r][c];
		}
	}
	return cloneMap;
}

 

이번에는 직접 하나하나 대입했으니 괜찮지 않을까?

 

하지만 이렇게 해도 안 된다. 그 이유는 ‘객체’이기 때문이다

객체를 저렇게 대입하면 객체의 주소 값이 대입 되고, 이는 단순히 주소를 복사한 것이 된다. 결국 clone한 결과 값인 cloneMap에서 값을 바꾸면 주소로 직접 바꾸게 되는 것이기 때문에 map의 값도 자동적으로 바뀌게 된다.

 

우리가 복사를 하는 목적은 복사한 객체를 변경해도 원본에 영향을 가지 않게 하기 위함이다. 그런데 이렇게 해버리면 clone한 객체를 사용해도 원본 값이 계속 바뀌게 되는 것이고.. 그래서 답이 매우 이상하게 나온다.

 

그래서 결론은 어떻게 해야 할까?

기억 상 여러가지 방법이 있었던 것 같은데 일단 나는 다음과 같은 방법으로 해결했다.

그건 바로 clone 시 새로운 Object 객체를 만들어서 대입해주는 것이다.

 

그래서 다음과 같은 코드로 해결이 가능하다.

    private static Fish[][] myClone(Fish[][] map) {
        Fish[][] newClone = new Fish[R][C];
        for (int r = 0; r < R; r++){
            for (int c = 0; c < C; c++){
                if (map[r][c] != null){
                    newClone[r][c] = new Fish(map[r][c].no, map[r][c].dir);
                }
            }
        }
        return newClone;
    }

 

물고기 번호

물고기 정보를 fish 배열에 따로 저장했는데, 문제에서는 물고기 번호가 1번 ~ 16번이었다. 그런데 인덱스로 0~15로 나타내기 위해서 입력 값에서 1을 빼주면서 받았는데, 그러면 물고기 번호가 줄어든다. 상어가 물고기를 먹을 때 이를 주의해서 1씩 더 더해주어 해결했다.

 

---

 

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G2_19236_청소년상어 {

    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static class Fish{
        int no;
        int dir;
        public Fish(int no, int dir){
            this.no = no;
            this.dir = dir;
        }

        @Override
        public String toString() {
            return "no " + no + " dir " + dir;
        }
    }
    static int R, C, N;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        R = 4;
        C = 4;
        N = 16;

        Pos[] fish; //N마리의 물고기 순서대로. 위치정보 담고있음
        Fish[][] map; //맵

        map = new Fish[R][C];
        fish = new Pos[N];
        //입력
        for (int r = 0; r < R; r++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int c = 0; c < C; c++){
                int no = Integer.parseInt(st.nextToken()) - 1; //0~15
                int dir = Integer.parseInt(st.nextToken()) - 1; //0~7

                //맵과 fish에 각각 저장
                map[r][c] = new Fish(no, dir);
                fish[no] = new Pos(r, c);
            }
        }

        //logic
        //1. 청소년 상어가 (0,0)에 들어가 물고기를 먹음(방향)
        int deleteFishNo = map[0][0].no;
        int deleteFishDir = map[0][0].dir;

        Pos sharkPos = new Pos(0, 0);
        int sharkDir = deleteFishDir;
        fish[deleteFishNo] = null;
        map[0][0] = null;

        //2. 물고기 이동
        dfs(sharkPos, sharkDir, fish.clone(), myClone(map), deleteFishNo+1);

        System.out.println(result);
    }

    private static Fish[][] myClone(Fish[][] map) {
        Fish[][] newClone = new Fish[R][C];
        for (int r = 0; r < R; r++){
            for (int c = 0; c < C; c++){
                if (map[r][c] != null){
                    newClone[r][c] = new Fish(map[r][c].no, map[r][c].dir);
                }
//                newClone[r][c] = map[r][c]; //안됨!!!!!
            }
        }
        return newClone;
    }

    static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dc = {0, -1, -1, -1, 0, 1, 1, 1};
    static int result = 0;
    private static void dfs(Pos sharkPos, int sharkDir, Pos[] fish, Fish[][] map, int eat){
        //물고기 이동
        for (int i = 0; i < N; i++){
            if (fish[i] != null){
                //물고기가 판에 존재하면 한 칸씩 이동
                Pos cur = fish[i];
                Fish originInfo = map[cur.r][cur.c];

                //한 칸 이동한 위치 구함. 이동할 수 있는 위치를 구할동안 45도 반시계 회전.
                for (int k = 0; k < 8; k++){ //360도 회전
                    int nr = cur.r + dr[originInfo.dir];
                    int nc = cur.c + dc[originInfo.dir];
                    //범위를 벗어나거나 상어의 위치이면 이동 못 함. 회전
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C ||
                            (sharkPos.r == nr && sharkPos.c == nc)) {
                        originInfo.dir = (originInfo.dir + 1) % 8;
                    }
                    else{
                        //이동할 수 있으면 자리 바꾸고 중단
                        //새로운 자리 정보
                        Fish otherFish = map[nr][nc];
                        Pos otherPos = new Pos(nr, nc);

                        //현재 물고기 이동
                        map[nr][nc] = originInfo;
                        fish[originInfo.no] = otherPos;

                        //다른 물고기 현재 자리로 이동
                        map[cur.r][cur.c] = otherFish; //null이면 null 들어가게
                        if (otherFish != null){
                            fish[otherFish.no] = new Pos(cur.r, cur.c);
                        }

                        break;
                    }
                }
            }
        }

        //상어 이동 : 상어가 가진 방향으로 +1 씩 더해가면서.. 경계 넘으면 중단
        int nr = sharkPos.r;
        int nc = sharkPos.c;
        while(true){
            nr += dr[sharkDir];
            nc += dc[sharkDir];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) break;
            if (map[nr][nc] == null) continue; //빈칸으로는 못 감

            //물고기가 있으면 거기로 갈 수 있음. 잡아먹음.
            Fish dead = map[nr][nc];

            //피쉬, 맵 복사
            Pos[] fishClone = fish.clone();
            Fish[][] mapClone = myClone(map);
            //피쉬, 맵 업뎃
            fishClone[dead.no] = null;
            mapClone[nr][nc] = null;

            dfs(new Pos(nr, nc), dead.dir, fishClone, mapClone, eat + dead.no + 1);
        }
        result = Math.max(result, eat);
    }
}