[백준 스터디 9주차] 19237 어른상어 골드3 - 자바(Java)/ 삼성 기출문제/ 시뮬레이션

📑 문제

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

19237번: 어른 상어

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

시작상태

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

 

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

 

 

 

 

 

 

 

 

✒️ 풀이

✔️ 전체적인 흐름은 다음과 같다.

 ◻️ 0초에 입력된 상어들을 위치시키고, 지도에 냄새까지 묻혀둔다.

 ◻️ 상어들의 이동을 반복하는 무한루프에 들어간다.

 ◻️ 무한루프의 코드 순서: 1초 증가(새로운 단계를 의미) > 방문 배열 초기화 > 상어들 이동 > 이동위치에 냄새 묻히기 > 종료조건 확인

 ◻️ 제일 쎈 1번 상어부터 순서대로 정보를 가져와 이동위치를 찾는다.

 ◻️ 사방탐색 후, 냄새가 없거나 지워진 빈 곳이 있다면 그 곳을 이동위치로 정한다. 이동할 곳이 없다면 현재 상어의 냄새가 있는 곳으로 정한다. (모든 이동은 각 상어에 저장된 방향 별 이동순위에 따른다)

 ◻️ 정해진 이동위치에 이미 상어가 존재한다면(방문배열에 기록되어 있다) 더 쎈 상어가 이미 와 있다는 뜻이므로, 이 상어는 쫓겨난다.

 ◻️ 아무도 없다면 해당 위치로 상어 정보를 업데이트 시켜준다. 방문배열도 기록해준다.

 ◻️ 모든 상어 별로 이동이 끝나면, 방문배열을 완탐하여 상어가 위치한 곳에 냄새를 묻혀준다.

 ◻️ 한 마리만 남았는지(1번 상어), 종료 조건을 확인한다.

 

✔️ 상어의 위치와 보고있는 방향을 저장할 구조체(SHARK)를 만들었다.

 ◻️ 상어 구조체의 배열 sharks를 선언해서 x번 상어의 정보에(sharks[x]) 쉽게 접근할 수 있도록 했다.

 

✔️ 각 상어의 보고있는 방향 별 다음 이동방향 순서는 3차원 배열(priorities)을 통해 정리했다.

 ◻️ 문제에서 제시한 방향 인덱스(1~4)는 인덱스 접근에 편리하게 0~3으로 고쳐 썼다.

 ◻️ priorities[shark number][current direction][order] = next direction

 ◻️ 예를 들어 priorities[1][0][1]=3: 1번 상어가 위(0)방향일 때 두 번째(1)로 살펴볼 방향 인덱스는 오른쪽(3)이라는 뜻이다.

 

💡 냄새를 묻히고, 냄새가 남아있는지 보고, 자신의 냄새가 있는 곳을 찾는 것은 모두 3차원 배열(map)을 통해 정리했다.

 ◻️ map[i][j][0]: (i,j)에 냄새를 묻힌 상어의 번호

 ◻️ map[i][j][1]: (i,j)에 남은 냄새가 유효한 시간

 ◻️ 냄새가 K번 이동해야 지워진다는 것은, (냄새를 묻힌 시간+K초) 이후부터 그 위치에 접근할 수 있다는 뜻이다. 즉, K=4일 때 0초에 묻힌 냄새는 1초>2초>3초>4초 후 5초부터 사라지고 접근할 수 있는 곳이 된다.

 

✔️ 상어를 쫓는 것은 쎈 상어부터 이동시키는 것과 방문배열을 설정하는 것으로 대신했다.

 ◻️ 상어들의 이동위치가 겹치면 제일 작은 번호의 상어만 남는다. 이 뜻은 제일 작은 상어부터 이동시킨 다음, 후에 위치가 겹치는 놈은 그냥 지워버리면 된다는 뜻이다.

 ◻️ 이를 위해 방문배열(visited)를 선언했다. 상어가 이동할 위치가 정해지면 방문배열을 확인하여, 해당 위치가 비어 있으면 이동하고, 그 곳에 이미 상어가 존재한다면 현재의 상어는 상어배열(sharks)에서 지워버린다(null).

 

 

 

 

🚫 조심할 것 🚫 

 ✔️ 냄새 묻히기는 무조건 모든 상어가 이동한 후에, 쫓겨날 놈은 쫓아내고 해야 한다! 각 상어를 이동시킬 때 냄새 묻히기까지 동시에 해버린다면, 그 다음 상어는 자신도 이동할 수 있는 위치임에도 불구하고 '냄새가 이미 묻어있구나' 생각하여 그 곳을 이동위치로 고려하지 않는다.

 

 ✔️ 6%에서 오류가 났는데, 시간이 1000일 때 조건을 제대로 따지지 못했기 때문이다.

 ◻️ (종료조건 1) 개체 수가 1이면 끝내기/ (종료조건 2) 시간이 1000이 넘으면 -1로 바꾸고 끝내기 >>> 아님

 ◻️ 위처럼 짜놨더니 time=1000일 때 두 마리가 남고 time=1001일 때 한 마리가 남은 경우, time=1001에서 조건1이 충족되어 조건2까지 가지 못하고 루프를 종료시키는 오류가 생겼다. -1이 아닌 1001이 출력된 것이다.

 ◻️ 위 오류를 잡기 위해 종료조건 순서를 바꿔주었다. 아니면 if(time==1000 && cnt>1)로 조건2를 바꿔줘도 되겠다.

     

 

 

 

 

 

 

 

🙋‍♀️ 의견

 나를 정말 많이 애먹인 어른상어....😩

 몇 번을 다시 풀고 고쳐도 자꾸 틀리고, 디버깅도 쉽지가 않았다. 

 상어가 잘 이동했는지 확인하려면 (1.냄새가 지워진 곳으로 잘 갔는지/ 2.자기가 왔던 곳으로 돌아간게 맞는지/ 3.이동 방향 우선순위는 맞는지) 다 체크해야 했기 때문....

 

 결국 문제 풀기를 포기했지만 이 찜찜함(분명 나는 잘 풀었는데 왜?!)을 이길 수가 없더라...

 그래서 몇 달만에 다시 풀어봤더니 띠용 드디어 풀렸다. 분명 똑같은 로직으로 접근했던 것 같은데 예전에는 대체 뭐에 막혔던 걸까?(ㅋㅋ)

 아무튼....포기했던 문제를 다시 풀어내서 기분이 좋다~

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

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

/** https://www.acmicpc.net/problem/19237 */
public class Main_백준_19237_어른상어_골드2 {

    static class SHARK {
        int num, dir, r, c;
        public SHARK(int num, int dir, int r, int c) {
            this.num = num;
            this.dir = dir;
            this.r = r;
            this.c = c;
        }
    }

    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

    static int N, M, K;
    static int[][][] map;
    static int[][][] priorities;
    static SHARK[] sharks;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // [N][N][0]:SHARK NUMBER, [N][N][1]:INPUT TIME
        map = new int[N][N][2];
        sharks = new SHARK[M+1];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if(n!=0){ //상어 발견
                    sharks[n] = new SHARK(n,0,i,j);
                    map[i][j][0] = n;
                    map[i][j][1] = K;
                }
            }
        }//map input

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            int dir = Integer.parseInt(st.nextToken())-1;
            sharks[i].dir = dir;
        }//shark current direction input

        priorities = new int[M+1][4][4];
        for (int i = 1; i <= M; i++) {
            for (int j = 0; j < 4; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < 4; k++) {
                    priorities[i][j][k] = Integer.parseInt(st.nextToken())-1;
                }
            }
        }//direction priorities input

        int time=0, cnt=M;
        int[][] visited = new int[N][N];
        
        while (time<1000){
            time++;

            // 이동위치 기록 배열 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    visited[i][j] = 0;
                }
            }

            // 상어 이동 시작: 1번부터
            for (int i = 1; i <= M; i++) {

                // 이미 쫓겨난 상어인지 확인
                if(sharks[i]==null) continue;

                // 쎈 상어부터 움직이기(작은 번호)
                int shark = i;
                int dir = sharks[i].dir;
                int sharkR = sharks[i].r;
                int sharkC = sharks[i].c;
                boolean flag = false;

                // 1. 주변에 빈 곳을 찾는다.
                int nr = sharkR, nc = sharkC, newDir = dir;
                for (int j = 0; j < 4; j++) {//사방탐색
                    newDir = priorities[shark][dir][j];
                    nr = sharkR + dr[newDir];
                    nc = sharkC + dc[newDir];

                    if(nr<0||nc<0||nr>=N||nc>=N|| map[nr][nc][1]>=time) continue;

                    flag = true;
                    break;
                }
                // 2. 빈 곳이 없으면 자신의 냄새가 있는 곳을 잡는다.
                if(!flag){
                    for (int j = 0; j < 4; j++) {//사방탐색
                        newDir = priorities[shark][dir][j];
                        nr = sharkR + dr[newDir];
                        nc = sharkC + dc[newDir];

                        if(nr<0||nc<0||nr>=N||nc>=N||map[nr][nc][0]!=shark) continue;
                        else break;
                    }
                }

                //겹치는 상어가 있는지 확인
                if(visited[nr][nc]!=0){
                    sharks[i] = null;
                    cnt --;
                    continue;
                }
                else visited[nr][nc] = shark;

                //상어위치 업데이트
                sharks[i].r = nr;
                sharks[i].c = nc;
                sharks[i].dir = newDir;

            }//end of shark's movement

            // 3. 이동한 위치로 지도 정보 업데이트
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(visited[i][j]==0) continue;

                    map[i][j][0] = visited[i][j];
                    map[i][j][1] = time+K;
                }
            }

            if(time>1000){
                time=-1;
                break;
            }
            if(cnt==1) break;

        }//end of endless loop

        System.out.println(time);
        
    }//end of main
}//end of class

 

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨