이번에 풀어본 문제는
백준 19237번 어른 상어 입니다.

📕 문제 링크

❗️코드

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

class Smell
{
    int num,time;

    public Smell(int num, int time)
    {
        this.num = num;
        this.time = time;
    }
}
class Shark2
{
    int x,y,dir,num;

    public Shark2(int num, int x, int y, int dir)
    {
        this.num = num;
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    public Shark2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static boolean [][] map;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    static List<Integer> [][] dir_info;
    static int N,M,K;
    static Smell [][] smell;
    static PriorityQueue<Shark2> pq;
    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());

        map = new boolean[N][N];
        smell = new Smell[N][N];
        Shark2 [] tmp_arr = new Shark2[M];

        for(int i = 0; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; ++j)
            {
                int tmp = Integer.parseInt(st.nextToken());
                if(tmp > 0)
                {
                    map[i][j] = true;
                    tmp_arr[tmp-1] = new Shark2(i,j);
                }
            }
        }

        pq = new PriorityQueue<>(new Comparator<Shark2>() {
            @Override
            public int compare(Shark2 o1, Shark2 o2) {
                return o1.num - o2.num;
            }
        });

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; ++i)
        {
            int tmp_x = tmp_arr[i].x;
            int tmp_y = tmp_arr[i].y;
            int tmp_dir = Integer.parseInt(st.nextToken())-1;
            pq.add(new Shark2(i+1,tmp_x,tmp_y,tmp_dir));
            smell[tmp_x][tmp_y] = new Smell(i+1,K);
        }

        dir_info = new ArrayList[M][4];
        for(int i = 0; i < M; ++i)
        {
            for(int j = 0; j < 4; ++j)
            {
                st = new StringTokenizer(br.readLine());
                dir_info[i][j] = new ArrayList<>();
                while(st.hasMoreTokens()) dir_info[i][j].add(Integer.parseInt(st.nextToken())-1);
            }
        }
        int t = 0;
        while(t++ < 1000)
        {
            Queue<Shark2> tmp_q = new LinkedList<>();
            next : while(!pq.isEmpty())
            {
                Shark2 cur = pq.poll();
                map[cur.x][cur.y] = false;
                // 빈칸탐색
                for(int idx = 0; idx < 4; ++idx)
                {
                    int dir = dir_info[cur.num-1][cur.dir].get(idx);
                    int mx = cur.x + dx[dir];
                    int my = cur.y + dy[dir];

                    if(!isValid(mx,my) || smell[mx][my] != null) continue;
                    if(!map[mx][my])
                    {
                        map[mx][my] = true;
                        tmp_q.add(new Shark2(cur.num,mx,my,dir));
                    }
                    continue next;
                }

                // 자신의 냄새 탐색
                for(int idx = 0; idx < 4; ++idx)
                {
                    int dir = dir_info[cur.num-1][cur.dir].get(idx);
                    int mx = cur.x + dx[dir];
                    int my = cur.y + dy[dir];

                    if(!isValid(mx,my) || smell[mx][my] == null || map[mx][my]) continue;
                    if(smell[mx][my].num == cur.num)
                    {
                        map[mx][my] = true;
                        tmp_q.add(new Shark2(cur.num,mx,my,dir));
                        continue next;
                    }
                }
            }

            for(int i = 0; i < N; ++i) // 냄새 지속시간 감소
            {
                for(int j = 0; j < N; ++j)
                {
                    if(smell[i][j] != null)
                    {
                        if(smell[i][j].time > 1) smell[i][j].time--;
                        else smell[i][j] = null;
                    }
                }
            }

            while(!tmp_q.isEmpty())
            {
                Shark2 cur = tmp_q.poll();
                pq.add(cur);
                smell[cur.x][cur.y] = new Smell(cur.num,K);
            }

            if(pq.size() == 1) break;
        }

        int answer = t == 1001 ? -1 : t;
        System.out.print(answer);
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

상어들이 각자 정해진 방향 우선순위에 맞게 이동을 진행하며, 자신보다 숫자가 낮은 상어를 같은 좌표에서 만났을 경우 격자 밖으로 쫓겨나는 문제입니다.
상어들이 이동할 때마다 자신의 냄새를 남기기 때문에, 냄새의 정보를 저장하는 smell 2차원 배열을 사용했고, 현재 남아있는 상어는 우선순위 큐에 담깁니다. 상어의 숫자가 작을수록 강한 상어이기 때문에, 강한 상어를 우선적으로 이동시킨 후, 다음 순서의 상어가 이동을 진행할 때 가야할 좌표에 앞서 이동한 상어가 존재한다면 바로 넘겨주어 다음 반복에서는 해당 번호의 상어를 제외시켜주면 됩니다.
따라서 위의 반복으로 최대 1000초 진행하며 우선순위 큐의 사이즈가 1이되는 순간, 즉 1번 상어만 남는 순간 반복문을 벗어나게 됩니다.
반복문을 벗어난 시점에 t값이 1001이라면 모든 반복을 진행한 것이므로 1000초동안 결과가 나오지 않은것이며 -1을 출력, 이외의 경우에는 t값을 그대로 출력하면 해결됩니다.

📜 후기

복잡한 입력으로 주어지는 방향 우선순위들만 정리해주면 생각보다 간단한 문제였습니다. 오랜만에 풀어서 조금 헷갈렸지만 어렵지않게 해결했습니다!
최근 여러 전형이 너무 많이 겹쳐서, 알고리즘 공부를 잠시 뒤로 미뤄두고 시험 공부에 올인했습니다ㅠ 좋은 결과를 기다리며.....다시 달려보도록 할게요!