[백준 19236, Java] 청소년 상어

문제

www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

풀이

문제 순서대로 상어 현재위치의 물고기를 먹는다 → 물고기가 이동한다→ 상어가 이동한다 를 구현하면 된다. 이때 문제에서 힌트를 준다고 생각했던 부분이 예시였다. in[][] map을 선언해서 여기에는 물고기번호와 상어를 표시했다. 그런다음 "번호순서대로 물고기가 이동한다"를 구현해 주기 위해서 Fish[] fishArray를 선언한 후, 각 인덱스가 물고기 번호라고 생각하고 물고기 정보를 저장했다. 

 

헤매던 부분

1.객체배열 복사 →null point error

2.Fish fish = fishArray[index]에서 fish를 변경했을 때 fishArray도 변경이 되는지 →객체는 주소를 복사!

3. 방향 : 문제에서 주어진건 1~8. 따라서 int[] dx = {~}에서 0~7로 구현했다면 입력받을 때 -1 해야한다

4. 상어 현재위치의 물고기를 먹는다 → 물고기가 이동한다→ 상어가 이동한다를 구현할 때 무엇이 변하는 지 : 상어 현재위치의 물고기를 먹었다면, 상어의 방향변경, 상어의 먹은 물고기 번호 증가, map[][]에서 상어위치 변경, fishArray에서 물고기 삭제

소스

 

보완해야할 부분

이런문제 디버깅을 어떻게 하면 효율적으로 할 수 있을까.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class Shark{
    int x, y, direction, eatFishNumber;
    Shark(int x, int y, int direction, int eatFishNumber){
        this.x =x;
        this.y =y;
        this.direction =direction;
        this.eatFishNumber = eatFishNumber;
    }
    public String toString() {
        return "x:"+x+",y:"+y+"direction:"+direction+"eatFishNumber:"+eatFishNumber;
    }
}
class Fish{
    int x, y, direction, number;
    Fish(int x, int y, int direction, int number){
        this.x = x;
        this.y = y;
        this.direction =direction;
        this.number = number;
    }
    @Override
    public String toString() {
        return "x:"+x+",y:"+y+"direction:"+direction+"number:"+number;
    }
}
public class Main {
    static final int EMPTY = 0;
    static final int SHARK = -1;

    static int[] dx = {-1,-1,-1,0,1,1,1,0};
    static int[] dy= {1,0,-1,-1,-1,0,1,1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int[][] map = new int[4][4];
        Fish[] fishArray  = new Fish[17];
        Shark shark = new Shark(0, 0, 0, 0);

        for(int r=0;r<4;r++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0;c<4; c++) {
                int number = Integer.parseInt(st.nextToken());
                int direction = Integer.parseInt(st.nextToken())%8;

                map[r][c] = number;
                fishArray[number] = new Fish(r,c,direction,number);
            }
        }

        int result = getMaxFishNumber(shark,map,fishArray);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    static int getMaxFishNumber(Shark shark, int[][] oriMap, Fish[] oriFishArray) {
        //맵복사
        int[][] map = new int[4][4];
        Fish[] fishArray = new Fish[17];
        copyMap(oriMap, map);
        copyArray(oriFishArray,fishArray);


        //현재 상어위치에 있는 물고기를 먹는다
        Fish eatFish =fishArray[map[shark.x][shark.y]];
        map[shark.x][shark.y] = SHARK;
        fishArray[eatFish.number] = null;

        shark.direction = eatFish.direction;
        shark.eatFishNumber += eatFish.number;




        //물고기 이동
        for(int number = 1; number<=16; number++) {
            Fish moveFish = fishArray[number];
            if(moveFish!=null) {

                int x = moveFish.x;
                int y = moveFish.y;
                int direction = moveFish.direction;
                for(int d=0;d<8;d++) {
                    int nx = x + dx[direction];
                    int ny = y + dy[direction];

                    if(isValid(nx,ny)) {
                        if(map[nx][ny]!=SHARK) {
                            if(map[nx][ny]==EMPTY) {
                                moveFish.x = nx;
                                moveFish.y = ny;
                                moveFish.direction =direction;

                                map[nx][ny] = moveFish.number;
                                map[x][y] = EMPTY;
                            }
                            else {
                                Fish changeFish = fishArray[map[nx][ny]];

                                map[x][y]  = changeFish.number;
                                map[nx][ny] = moveFish.number;

                                changeFish.x = x;
                                changeFish.y = y;
                                moveFish.x = nx;
                                moveFish.y = ny;
                            }
                            break;
                        }
                    }

                    direction = (direction+1)%8;
                    moveFish.direction =direction;
                }
            }
        }


        //상어이동
        int maxFishNumber = shark.eatFishNumber;
        int x = shark.x;
        int y = shark.y;
        map[x][y] = EMPTY;
        for(int count = 0; count<4; count++) {
            int nx = x + dx[shark.direction];
            int ny = y + dy[shark.direction];

            if(isValid(nx, ny)) {
                if(map[nx][ny]!=EMPTY) {
                    Shark moveShark = new Shark(nx, ny, shark.direction, shark.eatFishNumber);
                    int result = getMaxFishNumber(moveShark, map, fishArray);
                    maxFishNumber = Math.max(maxFishNumber, result);
                }
            }
            x= nx;
            y =ny;
        }

        return maxFishNumber;

    }
    static boolean isValid(int x, int y) {
        return x>=0 && y>=0 && x<4 && y<4;
    }

    static void copyMap(int[][] source, int[][] dest) {
        for(int r=0; r<source.length;r++) {
            for(int c=0;c<source[r].length;c++) {
                dest[r][c] = source[r][c];
            }
        }
    }

    static void copyArray(Fish[] source, Fish[] dest) {
        for(int index =0; index<source.length;index++) {
            if(source[index]!=null) {
                dest[index] = new Fish(source[index].x, source[index].y, source[index].direction, source[index].number);
            }
        }
    }

    static void printMap(int[][] map) {
        for(int r=0; r<map.length;r++) {
            for(int c=0;c<map[r].length;c++) {
                System.out.print(map[r][c]+" ");
            }
            System.out.println();
        }
    }
}