[백준 19237, Java] 어른상어

문제

www.acmicpc.net/problem/19237

19237번: 어른 상어

 

풀이

 처음 접근이 어려웠던 건, 어떤 변수들이 필요한지를 구체적으로 생각하지 못했기 때문이다.

 

"상어가 있고, 냄새가 있으며 상어가 이동을 할 때 냄새를 뿌린다"를 프로그래밍 적으로 표현하면 "상어 객체가 있고(속성: 위치, 번호, 방향) 냄새객체가 있다(속성: 위치, 상어번호, 지속시간) 상어는 상하좌우인접한 칸으로 이동하고, 이동 후에는 해당위치에 냄새객체를 생성한다" 라고 할 수 있다.

 

그럼 여기서 어떤게 필요한 지 생각해보면, 상어가 상하좌우로 이동하기 때문에 이차원 배열이 필요하다. 이때 상어 객체에 대한 이차원배열로도 할 수 있지만, 이렇게 되면 N*N탐색을 해야한다고 생각해서 상어 객체를 생각했다. 즉 상어번호의 위치는 int[][]로 표현해주고, 상어에 대한 정보는 Shark[]에 담았다. 여기서 ArrayList가 아닌 Shark[]로 한 이유는, 상어배열의 인덱스와 상어의 번호를 동일하게 해서 접근하기 쉽게하기 위함이었다. 

 

 

보완해야 하는 것

1. 반복단위(초) 내에서의 순서

처음에는 냄새뿌리기 -> 상어이동 -> 냄새카운트 감소 이렇게 구현을 했는데, 이렇게 되면 상어가 이동했을 때 생성된 냄새의 초도 일괄 -1이 된다.

 

 "맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다." 를 보면 그 후 1초마다 이후(상어이동 ->냄새카운트 감소-> 냄새뿌리기 ) 의 순서로 해야함을 알 수 있다.

 

 

2. ArrayList로 풀때의 주의사항

1) 순회는 뒤에서 부터

상어리스트를 순회할 때 index =0 부터 하게되면 ArrayIndexOutOfBounds 에러가 난다. 이유는 for문 아래에서 영역밖으로 나가는 상어를 remove를 하게 되는데, 이때 size가 변하기 때문. 따라서 

 

for(int number = 1; number<=M; number++) 로 해줘야 한다

 

 

틀린 것

아래의 부분은 상어가 이동하려는 칸에 자신보다 큰 숫자의 상어가 있는 경우에 대한 로직이다. 

else if(moveShark.number<sharkMap[nx][ny]){
  sharkMap[moveShark.x][moveShark.y] = 0;
  sharkMap[nx][ny] = moveShark.number;

  sharkList[moveShark.number].x = nx;
  sharkList[moveShark.number].y = ny;
  sharkList[moveShark.number].direction = moveDirection;

  sharkList[sharkMap[nx][ny]] = null;
}

 

여기서 틀린부분이 있다. 이동하려는 곳에 있는 상어(번호가 큰 상어)를 삭제해야하는데, 

 

sharkMap[nx][ny] = moveShark.number로 업데이트 해놓고서 sharkList[sharkMap[nx][ny]]=null로 하게되면, 현재 상어 즉 번호가 작은 상어 정보가 사라지게 된다. 

 

근데 이 코드가 Shark[]로 했을 때는 통과가 된다. 그 이유는 Shark[]를 순회할 때 number=1인 상어부터 오름차순으로 순회하기때문에 이동하려고하는 곳에 있는 상어는 항상 번호가 작을 수 밖에 없다. 

 

그래서 number=1 number<=N 의 순서대로 순회하게 되면 위의 로직은 처리가 안된다. 

 

올바르게 고치면 아래와 같다

else if(moveShark.number<sharkMap[nx][ny]){
  sharkList[sharkMap[nx][ny]] = null;
  
  sharkMap[moveShark.x][moveShark.y] = 0;
  sharkMap[nx][ny] = moveShark.number;

  sharkList[moveShark.number].x = nx;
  sharkList[moveShark.number].y = ny;
  sharkList[moveShark.number].direction = moveDirection;

  
}

 

코드(Shark[] 풀이)

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, number, direction;
    Shark(int x, int y, int number, int direction){
        this.x = x;
        this.y =y;
        this.number = number;
        this.direction = direction;
    }

    @Override
    public String toString() {
        return "Shark{" +
                "x=" + x +
                ", y=" + y +
                ", number=" + number +
                ", direction=" + direction +
                '}';
    }
}
class Smell{
    int sharkNumber, timeLeft;
    Smell(int sharkNumber, int timeLeft){
        this.sharkNumber = sharkNumber;
        this.timeLeft = timeLeft;
    }

    @Override
    public String toString() {
        return "Smell{" +
                "sharkNumber=" + sharkNumber +
                ", timeLeft=" + timeLeft +
                '}';
    }
}

public class Main {
    static int N;
    static int M;
    static int K;

    static int[][] sharkMap;
    static Shark[] sharkList;
    static Smell[][] smellLMap;
    static int[][][] priorDirection;

    static int[] dx ={-1,1,0,0};
    static int[] dy ={0,0,-1,1};
    static final int UP = 0;
    static final int DOWN = 1;
    static final int LEFT = 2;
    static final int RIGHT = 3;

    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;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        sharkMap = new int[N][N];
        sharkList = new Shark[M+1];
        smellLMap = new Smell[N][N];
        priorDirection = new int[M+1][4][4];

        for(int r =0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                int value = Integer.parseInt(st.nextToken());
                sharkMap[r][c] = value;
                if(value>0){
                    sharkList[value] = new Shark(r,c,value,-1);
                }
            }
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int number = 1; number<=M; number++){
            sharkList[number].direction = Integer.parseInt(st.nextToken())-1;
        }

        for(int number = 1; number<=M; number++){
            for(int d =0; d<4; d++){
                st = new StringTokenizer(br.readLine()," ");
                for(int p = 0; p<4; p++){
                    priorDirection[number][d][p] = Integer.parseInt(st.nextToken())-1;
                }
            }
        }


        //냄새지도 초기화
        for(int number = 1; number<=M; number++){
            Shark shark = sharkList[number];
            smellLMap[shark.x][shark.y] = new Smell(shark.number, K);
        }

        int result = getSecond();
        bw.write(String.valueOf(result));
        bw.flush();

    }
    static int getSecond(){
        int second = 1;
        //틀린부분1 : 처음에 < 1000 라고 해서 틀림
        while(second<=1000){
            //상어이동
            for(int number = 1; number<=M; number++){
                if(sharkList[number]!=null){
                    Shark moveShark = sharkList[number];

                    int mySmellDirection = -1;
                    int moveDirection = -1;
                    boolean isMoved = false;

                    //상어 이동방향 구하기
                    for(int p =0; p<4;p++){
                        int nx = moveShark.x + dx[priorDirection[number][moveShark.direction][p]];
                        int ny = moveShark.y + dy[priorDirection[number][moveShark.direction][p]];

                        if(nx>=0 && ny>=0&& nx<N && ny<N){
                            if(smellLMap[nx][ny] == null){
                                isMoved = true;
                                moveDirection = priorDirection[number][moveShark.direction][p];
                                break;
                            }
                            else {
                                //틀린부분2 : mySmellDirection <- 자기 방향이 여러개일 때도 우선순위 고려해야
                                if(mySmellDirection ==-1){
                                    if(smellLMap[nx][ny].sharkNumber == moveShark.number){
                                        mySmellDirection = priorDirection[number][moveShark.direction][p];
                                    }
                                }
                            }
                        }
                    }

                    if(!isMoved) moveDirection = mySmellDirection;


                    //이동항향으로 이동
                    int nx = moveShark.x + dx[moveDirection];
                    int ny = moveShark.y + dy[moveDirection];

                    //이동하려는 방향에 다른 상어가 있는지 확인
                    if(sharkMap[nx][ny]==0){
                        sharkMap[moveShark.x][moveShark.y] = 0;
                        sharkMap[nx][ny] = moveShark.number;

                        sharkList[moveShark.number].x = nx;
                        sharkList[moveShark.number].y = ny;
                        sharkList[moveShark.number].direction = moveDirection;
                    }
                    else if(moveShark.number<sharkMap[nx][ny]){
                        sharkMap[moveShark.x][moveShark.y] = 0;
                        sharkMap[nx][ny] = moveShark.number;

                        sharkList[moveShark.number].x = nx;
                        sharkList[moveShark.number].y = ny;
                        sharkList[moveShark.number].direction = moveDirection;

                        sharkList[sharkMap[nx][ny]] = null;
                    }
                    else{
                        sharkMap[moveShark.x][moveShark.y] =0;
                        sharkList[moveShark.number] = null;
                    }
                }
            }

            //냄새 카운트 -1
            for(int r =0; r<N; r++){
                for(int c=0; c<N; c++){
                    if(smellLMap[r][c]!=null){
                        --smellLMap[r][c].timeLeft;

                        if(smellLMap[r][c].timeLeft==0){
                            smellLMap[r][c] = null;
                        }
                    }
                }
            }


            //냄새뿌리기
            for(int number = 1; number<=M; number++){
                Shark shark = sharkList[number];

                if(shark!=null){
                    smellLMap[shark.x][shark.y] = new Smell(shark.number, K);
                }
            }


            //남아있는 상어확인
            if(isNumberOneLeft()){
                return second;
            }

            ++second;
        }

        return  -1;
    }

    static boolean isNumberOneLeft(){
        for(int number = 2; number<=M; number++){
            if(sharkList[number]!=null){
                return false;
            }
        }
        return true;
    }

    static void printSharkMap(){
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                System.out.print(sharkMap[r][c]+" ");
            }
            System.out.println();
        }
    }

    static void printSmell(){
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                System.out.print(smellLMap[r][c]+" ");
            }
            System.out.println();
        }
    }
}

 

코드(ArrayList<Shark> 풀이)

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

class Shark implements Comparable<Shark>{
    int number, x, y, direction;
    Shark(int number, int x, int y, int direction){
        this.number = number;
        this.x = x;
        this.y = y;
        this.direction =direction;
    }

    @Override
    public int compareTo(Shark o) {
        return this.number-o.number;
    }

    @Override
    public String toString() {
        return "Shark{" +
                "number=" + number +
                ", x=" + x +
                ", y=" + y +
                ", direction=" + direction +
                '}';
    }
}
class Smell{
    int sharkNumber, timeLeft;
    Smell(int sharkNumber, int timeLeft){
        this.sharkNumber = sharkNumber;
        this.timeLeft = timeLeft;
    }
}
public class Main {
    static int N;
    static int M;
    static int K;

    static int[][] sharkMap;
    static ArrayList<Shark> sharkList;
    static Smell[][] smellMap;

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

    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;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K= Integer.parseInt(st.nextToken());

        sharkMap = new int[N][N];
        sharkList = new ArrayList<>();
        smellMap = new Smell[N][N];

        for(int r =0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                int value = Integer.parseInt(st.nextToken());
                sharkMap[r][c] = value;

                if(value!=0){
                    sharkList.add(new Shark(value, r, c, -1));
                }
            }
        }


        //초기 상어의 방향
        Collections.sort(sharkList);
        st = new StringTokenizer(br.readLine()," ");
        for(int index =0; index<sharkList.size();index++){
            sharkList.get(index).direction = Integer.parseInt(st.nextToken())-1;
        }

        //상어번호당 방향 우선순위
        directionPriority = new int[M+1][4][4];
        for(int number =1; number<=M; number++){
            for(int d = 0; d<4; d++){
                st = new StringTokenizer(br.readLine(), " ");
                for(int p =0; p<4; p++){
                    directionPriority[number][d][p] = Integer.parseInt(st.nextToken())-1;
                }
            }
        }

        int result =getSecond();
        bw.write(String.valueOf(result));
        bw.flush();


    }

    static int getSecond(){
        // 냄새 초기화
        for(int index = 0; index<sharkList.size(); index++){
            Shark shark = sharkList.get(index);
            if(shark!=null){
                smellMap[shark.x][shark.y] = new Smell(shark.number, K);
            }
        }

        int second = 1;


        while(second<=1000){
            // 상어 이동
            // 상어 이동방향 정하기

            for(int index = sharkList.size()-1; index>=0;index--){
                Shark moveShark = sharkList.get(index);

                int moveDirection = -1;
                int mySmellDirection = -1;
                boolean isMoved = false;

                for(int d = 0; d<4; d++){
                    int nx = moveShark.x + dx[directionPriority[moveShark.number][moveShark.direction][d]];
                    int ny = moveShark.y + dy[directionPriority[moveShark.number][moveShark.direction][d]];

                    if(nx>=0 && ny>=0 && nx<N && ny<N){
                        if(smellMap[nx][ny]==null){
                            isMoved = true;
                            moveDirection = directionPriority[moveShark.number][moveShark.direction][d];
                            break;
                        }
                        else{
                            if(smellMap[nx][ny].sharkNumber == moveShark.number){
                                if(mySmellDirection == -1){
                                    mySmellDirection = directionPriority[moveShark.number][moveShark.direction][d];
                                }
                            }
                        }
                    }
                }

                if(!isMoved) moveDirection = mySmellDirection;

                //이동방향으로 이동
                int nx = moveShark.x + dx[moveDirection];
                int ny = moveShark.y + dy[moveDirection];

                //이동하려는 방향에 상어가 있는지 없는지 확인
                if(sharkMap[nx][ny]==0){
                    sharkMap[moveShark.x][moveShark.y] = 0;
                    sharkMap[nx][ny] = moveShark.number;

                    moveShark.x = nx;
                    moveShark.y = ny;
                    moveShark.direction = moveDirection;
                }
                else{
                    if(moveShark.number<sharkMap[nx][ny]){
                        //이동할 위치에 있는 상어 삭제 <- 실수
                        for(int i = 0; i<sharkList.size(); i++){
                            if(sharkList.get(i).number == sharkMap[nx][ny]){
                                sharkList.remove(i);
                                break;
                            }
                        }


                        sharkMap[moveShark.x][moveShark.y] = 0;
                        sharkMap[nx][ny] = moveShark.number;

                        moveShark.x = nx;
                        moveShark.y = ny;
                        moveShark.direction = moveDirection;

                    }
                    else{
                        sharkMap[moveShark.x][moveShark.y] = 0;
                        sharkList.remove(moveShark);
                    }
                }

            }


            //냄새 초 -1 (0이면 소멸)
            for(int r=0; r<N; r++){
                for(int c=0; c<N; c++){
                    if(smellMap[r][c]!=null){
                        --smellMap[r][c].timeLeft;

                        if(smellMap[r][c].timeLeft==0){
                            smellMap[r][c] =null;
                        }
                    }
                }
            }
            //상어 현재위치에서 냄새 뿌리기
            for (Shark shark : sharkList) {
                smellMap[shark.x][shark.y] = new Smell(shark.number, K);
            }


            if(sharkList.size()==1){
                return second;
            }

            ++second;
        }
        return -1;
    }

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