[백준] code.plus(시뮬레이션과 구현,JAVA)19237번, 어른 상어

문제 링크

19237번: 어른 상어

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 상어가 같은 공간에 존재할 때 상어 번호가 낮은 상어가 높은 상어를 격자 밖으로 쫓아낸다.

2. 상어는 현재 방향에 따라 다음 이동의 우선순위가 존재한다.

3. 상어는 우선 빈 칸으로 이동하고 이동하지 못할 때에는 자신의 냄새가 남은 칸으로 이동한다.

4. 상어가 있던 장소에는 냄새가 남으며 K초 동안 존재한다.

5. 1번 상어가 혼자 존재할 때까지 지나간 초를 결과로 출력합니다.

6. 1000초가 넘어갔을 때 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 각 상어들을 이동을 실행하는 시뮬레이션을 진행합니다.

 

3. 시뮬레이션이 종료한 뒤 경과된 초를 결과로 출력합니다.

 

방향 우선순위

 

만약 상어의 우선 순위가

 

↑ : ↓ ← ↑ →

 

↓ : → ↑ ↓ ←

 

← : ← → ↓ ↑

 

→ : → ← ↑ ↓

 

현재 상어의 방향이 ↑이면

다음 이동할 방향을 탐색하는 순서는 ↓ ← ↑ →순입니다.

 

냄새

 

상어가 위치한 공간에 냄새를 남기며 냄새는 K초 동안 존재합니다.

 

코드에서는 space[][]배열에서 냄새가 존재할 수 있는 초를 저장하고 있습니다.

 

초가 space[][]값이 1~K값에서 0이 되었을 때 냄새가 사라지도록 index[][]의 값도 0으로 바꾸어줍니다.

 

 

예제입력 1

 

문제에 설명한 그림과 동일한 방식으로 진행됩니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력된 정보들을 띄어쓰기 기준으로 나누었습니다.
• start함수으로 모든 경우의 시뮬레이션을 진행합니다.
• 시뮬레이션 종료 후 경과된 초를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• start는 전체적인 시뮬레이션을 진행하며 1000초를 벗어나면 -1을 결과로 반환합니다.
• sharkMove는 상어가 이동하는 것을 진행합니다.
• spaceChange는 냄새의 경과된 초를 감소하는 것을 진행합니다.
• sharkCheck는 현재 공간에 1번 상어만 존재하는지 확인합니다.
• inSpace는 상어가 이동할 공간이 내부에 존재하는지 확인합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    //상어 정보 클래스
    static class shark{
        int x, y, d;
        boolean dead;	//상어 격자 밖으로 나갔는지 확인 변수
        public shark(int x, int y, int d, boolean dead) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.dead = dead;
        }
    }
    static int N,M,K;
    //index : 공간의 상어 냄새 번호, space : 공간의 냄새 유효 시간
    static int[][] index, space;
    static int[][][] direction;	//각 상어의 방향 우선순위 저장
    static ArrayList<shark> info = new ArrayList<>();	//상어 정보 저장 리스트
    static int[] dx = {0, 0, 0, -1, 1};	//상하좌우 x 변경값
    static int[] dy = {0, -1, 1, 0, 0};	//상하좌우 y 변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        index = new int[N][N];
        space = new int[N][N];
        direction = new int[M+1][5][5];
        for(int i=0;i<=M;i++)
            info.add(new shark(0,0, 0, false));
        //상어 정보 및 공간에 대한 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<N;j++){
                int x = Integer.parseInt(st.nextToken());
                if(x!=0){
                    index[i][j] = x;
                    space[i][j] = K;
                    info.get(x).x = j;
                    info.get(x).y = i;
                }
            }
        }
        //현재 상어 방향 정보 저장
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=M;i++)
            info.get(i).d = Integer.parseInt(st.nextToken());

        //상어 방향 우선순위 정보 저장
        for(int i=1;i<=M;i++){
            for(int j=1;j<5;j++){
                st = new StringTokenizer(br.readLine()," ");
                for(int s=1;s<5;s++)
                    direction[i][j][s] = Integer.parseInt(st.nextToken());
            }
        }
        int answer = start();	//시뮬레이션 시작 및 결과 저장
        bw.write(answer + "");	//경과된 초 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //시뮬레이션 진행하는 함수
    static int start(){
        int time = 0;
        while(true){
            //1000초를 초과시
            if(time>1000)
                return -1;	//-1 반환
            if(sharkCheck())	//1번 상어만 남았을 때
                break;
            sharkMove();	//상어 이동 진행
            time++;		//시간 증가
        }
        return time;	//경과된 초 반환
    }
    //상어 이동을 진행하는 함수
    static void sharkMove(){
        int[][] temp = new int[N][N];
        for(int i=1;i<=M;i++){
            shark cur = info.get(i);
            if(cur.dead)	//쫓겨난 상어는 넘기기
                continue;
            boolean moveCheck = false;	//상어가 이동했는지 확인 변수
            //상어 방향 우선순위에 따라 빈 칸 탐색 후 이동
            for(int j=1;j<=4;j++){
                int tempD = direction[i][cur.d][j];
                int tempX = cur.x + dx[tempD];
                int tempY = cur.y + dy[tempD];
                if(inSpace(tempX, tempY) && index[tempY][tempX]==0){
                    //이동한 칸에 더 낮은 번호 상어 존재시 쫓겨남
                    if(temp[tempY][tempX]!=0){
                        cur.dead = true;
                        break;
                    }
                    moveCheck = true;
                    cur.x = tempX;
                    cur.y = tempY;
                    cur.d = tempD;
                    temp[tempY][tempX] = i;
                    break;
                }
            }
            //빈 칸의 이동이 없을 때 우선순위에 따라 자신의 냄새가 존재하는 칸 탐색 후 이동
            if(!moveCheck){
                for(int j=1;j<=4;j++) {
                    int tempD = direction[i][cur.d][j];
                    int tempX = cur.x + dx[tempD];
                    int tempY = cur.y + dy[tempD];
                    if (inSpace(tempX, tempY) && index[tempY][tempX] == i) {
                        cur.x = tempX;
                        cur.y = tempY;
                        cur.d = tempD;
                        break;
                    }
                }
            }
        }
        spaceChange();	//냄새 시간 줄이기
        //상어 이동한 칸에 냄새 남기기
        for(int i=1;i<=M;i++){
            shark cur = info.get(i);
            if(cur.dead)
                continue;
            index[cur.y][cur.x] = i;
            space[cur.y][cur.x] = K;
        }
    }
    //냄새가 경과된 초를 줄이는 함수
    static void spaceChange(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(space[i][j]!=0)
                    space[i][j]--;
                if(space[i][j]==0)
                    index[i][j] = 0;
            }
        }
    }
    //1번 상어만 존재하는지 확인하는 함수
    static boolean sharkCheck(){
        for(int i=2;i<=M;i++){
            if(!info.get(i).dead)
                return false;
        }
        return true;
    }
    //상어의 이동이 공간 내부인지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x>=0 && y>=0 && x<N && y<N)
            return true;
        return false;
    }
}