알고리즘/시뮬레이션

BOJ 백준 19237 어른 상어 [JAVA]

kyjdummy 2025. 9. 28. 20:02

 

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

[ 문제 요약 ]

  • N*N 크기의 격자에 상어가 1~M까지 번호가 있고, 모든 번호는 서로 다르게 한 칸에 존재합니다.
  • 자기보다 번호가 큰 상어는 번호가 작은 상어가 모두 쫓아낼 수 있습니다.
  • 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌립니다. 그 후 1초마다 모든 상어가 동시에 상하좌우 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌립니다.
  • 냄새는 K 초 후 사라집니다. 상어가 이동 방향을 경정할 때는 인접 칸 중 아무 냄새가 없는 칸의 방향으로 갑니다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡습니다.
  • 이때 가능한 칸이 여러 개일 수 있는데, 그 경우 특정한 우선순위를 따릅니다.
  • 우선순위는 상어마다 다를 수 있고 같은 상어라도 현재 상어가 보고 있는 방향에 따라서도 다를 수 있습니다. 상어가 맨 처음 보고 있는 방향은 입력으로 주어지고, 그 후 방금 이동한 방향이 보고 있는 방향이 자기 방향입니다. 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 있으면 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨납니다.
  • 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 출력합니다.

 

[ 테스트 케이스 설명 ]

4 2 6 // 격자 크기(2<=20), 상어 수(2<=N^2), 냄세가 사라지는 초(1<=1000)
1 0 0 0 // 격자의 모습이 주어지고 상어번호가 1번부터 주어집니다.
0 0 0 0
0 0 0 0
0 0 0 2
4 3 // 상어의 각 방향이 주어짐, 1,2,3,4는 각 상 하 좌 우를 의미
1 2 3 4// 1번째 상어가 위를볼 때 우선순위
2 3 4 1// 1번째 상어가 아래를 볼 때 
3 4 1 2// 1번째 상어가 왼쪽을 볼 때
4 1 2 3// 1번째 상어가 오른족을 볼 때
1 2 3 4// 2번재 상어 정보 동일
2 3 4 1
3 4 1 2
4 1 2 3
1번 상어만 남게되는 초 : 26

 

[ 알고리즘 분류 ]

  • 구현
  • 시뮬레이션

 

[ 문제 해설 ]

 

문제만 잘 이해하면 크게 어렵지 않습니다.

 

상어는 규칙에 따라 이동합니다. 냄새가 없는 칸 먼저 탐색 후 있다면 이동하고 없다면 자기 자신이 지나온 길목을 탐색하여 이동합니다.

 

상어는 이동한 후 그 장소에 자기보다 순위가 큰 상어는 모두 내 쫓으므로 결과적으로 한 칸에 상어는 무조건 한 마리만 있게 됩니다.

 

이를 구현하기 위해 우선순위 큐를 사용합니다. 인덱스가 가장 작은 것이 가장 뒤로 가도록 우선순위 큐의 규칙을 정해 놓으면

한 장소에 상어가 한 마리 남도록 구현하기 쉽습니다.

 

[ 정답 코드 ]

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

class Main{
	
	static final int[][] dxy = {{-1,0},{1,0},{0,-1},{0,1}};
	static PriorityQueue<Shark>[][] map;
	static Shark[] shark;
	static int[][][] dir;// 각 상어마다의 우선 순위(상어인덱스 : 방향 : 우선순위)
	static int[][] smell;// 냄세가 사라지는 초
	static int[][] who;//어떤 상어인지
	static int N, M, K;
	static int sharkCnt;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 격자 크기(2<=20)
		M = Integer.parseInt(st.nextToken());// 상어 수(2<=N^2)
		K = Integer.parseInt(st.nextToken());// 냄세가 사라지는 초(1<=1000)
		sharkCnt = M;
		who = new int[N][N];
		smell = new int[N][N];
		dir = new int[M + 1][4][4];
		shark = new Shark[M + 1];
		map = new PriorityQueue[N][N];
		
		int pos[][] = new int[M + 1][2];// 상어의 방향을 입력 받고 그상어가 
		
		for(int y=0; y<N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++)
			{
				who[y][x] = Integer.parseInt(st.nextToken());// 상어 순번, 0이면 없는것
				map[y][x] = new PriorityQueue<>();
				
				if(who[y][x] != 0)
				{
					pos[who[y][x]][0] = y;
					pos[who[y][x]][1] = x;
					smell[y][x] = K;// 냄세가 사라지는 초
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int rank=1; rank<=M; rank++) // 상어의 첫 방향을 입력 받음
		{
			int dir = Integer.parseInt(st.nextToken()) - 1; // 방향은 -1을 줄여서 받음
			int y = pos[rank][0];
			int x = pos[rank][1];
			shark[rank] = new Shark(y, x, rank, dir);
		}
		
		for(int rank=1; rank<=M; rank++)// 상어 순위
		{
			for(int i=0; i<4; i++)// 각 상어마다의 상하좌우
			{
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<4; j++)// 각 방향마다 탐색 우선순위
					dir[rank][i][j] = Integer.parseInt(st.nextToken()) - 1;// 각 랭크별 상하좌우 우선순위를 받음 -1로 받음
			}
		}
		
		
		int time = 0;
		while(++time<1001)
		{
			for(int i=1; i<=M; i++)
			{
				Shark s = shark[i];
				
				if(s.out)// 아웃당한 상어면 스킵
					continue;
				
				boolean move = false;
				int pref[] = dir[s.rank][s.dir]; // 현 방향으로 순환 우선순위
				// 냄세가 없는 칸 먼저 탐색
				for(int dirIdx : pref)
				{
					int ny = s.y + dxy[dirIdx][0];
					int nx = s.x + dxy[dirIdx][1];
					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
					// 해당 좌표 냄세가 없으면 이동
					if(smell[ny][nx] < time)
					{
						s.y = ny;
						s.x = nx;
						s.dir = dirIdx;
						map[s.y][s.x].add(s);
						move = true;
						break;
					}
				}
				
				if(move)continue;
				
				// 자기 자신칸 탐색
				for(int dirIdx : pref)
				{
					int ny = s.y + dxy[dirIdx][0];
					int nx = s.x + dxy[dirIdx][1];
					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
					if(who[ny][nx] == s.rank)
					{
						s.y = ny;
						s.x = nx;
						s.dir = dirIdx;
						map[s.y][s.x].add(s);
						break;
					}
				}
				
			}
			
			kickOffAndMark(time);
			
			if(sharkCnt == 1)break;
		}
		
		if(time > 1000)
			time = -1;
		
		System.out.print(time);
	}
	static void kickOffAndMark(int time) {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(smell[y][x] <= time) who[y][x] = 0;
				
				while(map[y][x].size() > 1) // 자기보다 순위가 큰 애들은 내쫓음
				{
					Shark lose = map[y][x].poll();
					lose.out = true;
					sharkCnt--;// 상어수를 줄임
				}
				
				if(map[y][x].size() == 1)
				{
					Shark win = map[y][x].poll();
					who[y][x] = win.rank;// 자기 마킹
					smell[y][x] = time + K;// 냄세가 사라지는 초 설정
				}
			}
		}
	}
	static class Shark implements Comparable<Shark>{
		int y, x;
		int rank;
		int dir;
		boolean out;
		Shark(int y, int x, int rank, int dir){
			this.y = y;
			this.x = x;
			this.rank = rank;
			this.dir = dir;
			this.out = false;
		}
		@Override
		public int compareTo(Shark o) {
			return o.rank - this.rank;
		}
	}

}

 

[ 테스트 케이스 ]

5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
답 : 14

4 2 6
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
4 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
답 : 26

5 4 1
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
답 : -1

5 4 10
0 0 0 0 3
0 0 0 0 0
1 2 0 0 0
0 0 0 0 4
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
답 : -1

4 5 6
0 0 0 0
0 3 0 0
2 0 1 0
0 4 0 5
3 4 2 1 3
4 1 3 2
4 2 3 1
1 2 4 3
2 3 1 4
1 3 2 4
4 1 3 2
4 3 2 1
1 4 3 2
2 3 1 4
4 3 2 1
1 4 3 2
4 2 3 1
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
2 3 1 4
3 2 4 1
2 3 4 1
1 2 4 3
답 : 30


4 5 12
0 0 3 0
0 1 0 4
2 0 0 0
0 5 0 0
2 1 2 3 4
4 1 3 2
4 2 3 1
1 2 4 3
2 3 1 4
1 3 2 4
4 1 3 2
2 3 1 4
4 2 3 1
1 2 4 3
4 3 2 1
1 4 3 2
4 2 3 1
2 3 1 4
1 3 2 4
4 3 2 1
1 4 3 2
2 3 1 4
3 2 4 1
2 3 4 1
1 2 4 3
답 : 24



5 9 12
0 0 0 0 9
0 4 0 5 0
3 0 1 0 2
0 7 0 6 0
0 0 8 0 0
2 3 4 1 2 3 3 3 4
4 1 3 2
4 2 3 1
1 2 4 3
2 3 1 4
1 3 2 4
4 1 3 2
2 3 1 4
4 2 3 1
1 2 4 3
4 3 2 1
1 4 3 2
4 2 3 1
2 3 1 4
1 3 2 4
4 3 2 1
1 4 3 2
2 3 1 4
3 2 4 1
2 3 4 1
1 2 4 3
3 1 2 4
4 2 3 1
4 1 3 2
4 2 3 1
2 3 4 1
4 3 2 1
2 3 1 4
1 3 2 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
4 2 3 1
4 1 3 2
1 3 2 4
4 3 2 1
답 : 31

5 8 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 6 0 7 0
0 0 5 0 8
4 4 3 1 4 2 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
4 1 2 3
1 3 4 2
2 4 3 1
1 2 4 3
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
답 : 30

'알고리즘 > 시뮬레이션' 카테고리의 다른 글

BOJ 백준 21611 마법사 상어와 블리자드  (0) 2025.09.30
BOJ 백준 20061 모노미노도미노 2 [JAVA]  (0) 2025.09.29
BOJ 백준 17837 새로운 게임 2 [JAVA]  (0) 2025.09.28
BOJ 백준 19238 스타트 택시 [JAVA]  (0) 2025.09.23
BOJ 백준 17822 원판 돌리기 [JAVA]  (0) 2025.09.22

'알고리즘/시뮬레이션'의 다른글

  • 현재글BOJ 백준 19237 어른 상어 [JAVA]

관련글

티스토리툴바