[백준] 19237 - 어른 상어 (java)

문제

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

코드

import java.io.*;
import java.util.*;

class Shark {
	int x, y, d;

	public Shark(int x, int y, int d) {
		this.x = x;
		this.y = y;
		this.d = d;
	}
}

public class Main {
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, -1, 1 };
	static int N, M, k;
	static int[][][] priority;
	static int[][] map;
	static int[][] num;
	static int[][] smell;
	static Map<Integer, Shark> sharkMap = new HashMap<>();

	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 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		priority = new int[M + 1][5][5];
		map = new int[N + 1][N + 1];
		num = new int[N + 1][N + 1];
		smell = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {	// map 입력
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] > 0) {
					sharkMap.put(map[i][j], new Shark(i, j, 0));
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= M; i++) {	// 상어 방향 입력
			int d = Integer.parseInt(st.nextToken());
			sharkMap.get(i).d = d;
		}

		for (int i = 1; i <= M; i++) {	// 상어 방향 우선순위 입력
			for (int j = 1; j <= 4; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 1; k <= 4; k++) {
					priority[i][j][k] = Integer.parseInt(st.nextToken());
				}
			}
		}

		int cnt = 0;
		while (true) {
			cnt++;

			Map<Integer, Shark> temp = new HashMap<>();

			// 자기자리에 냄새 기록
			for (Integer key : sharkMap.keySet()) {
				Shark shark = sharkMap.get(key);
				smell[shark.x][shark.y] = k; 
				num[shark.x][shark.y] = key;
			}

			// 상어 다음 자리 찾기
			for (Integer key : sharkMap.keySet()) {
				Shark shark = sharkMap.get(key);

				boolean flag = false;
				for (int i = 1; i <= 4; i++) {
					int dir = priority[key][shark.d][i];
					int nx = shark.x + dx[dir];
					int ny = shark.y + dy[dir];

					if (nx > 0 && nx <= N && ny > 0 && ny <= N) {
						if (num[nx][ny] == 0) {
							temp.put(key, new Shark(nx, ny, dir));
							flag = true;
							break;
						}
					}
				}

				if (!flag) { // 빈칸이 없을 때
					for (int i = 1; i <= 4; i++) {
						int dir = priority[key][shark.d][i];
						int nx = shark.x + dx[dir];
						int ny = shark.y + dy[dir];

						if (nx > 0 && nx <= N && ny > 0 && ny <= N) {
							if (num[nx][ny] == key) {
								temp.put(key, new Shark(nx, ny, dir));
								break;
							}
						}
					}
				}
			}
			
			// 상어 자리 옮기기
			for (Integer key : temp.keySet()) {
				Shark cur = temp.get(key);

				map[sharkMap.get(key).x][sharkMap.get(key).y] = 0;

				if (map[cur.x][cur.y] != 0) { // 이미 상어가 있는 경우
					if (key > map[cur.x][cur.y]) {
						sharkMap.remove(key);
						continue;
					} else {
						sharkMap.remove(map[cur.x][cur.y]);
					}
				}

				map[cur.x][cur.y] = key;

				sharkMap.get(key).x = cur.x;
				sharkMap.get(key).y = cur.y;
				sharkMap.get(key).d = cur.d;
			}

			// smell 확인
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (smell[i][j] > 1) {
						smell[i][j]--;
					} else if (smell[i][j] == 1) {
						smell[i][j] = 0;
						num[i][j] = 0;
					}
				}
			}

			if (sharkMap.size() == 1) {
				break;
			}

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

		bw.write(cnt + "\n");
		bw.close();
		br.close();
	}
}

정리

N, M, k: 맵의 크기, 상어의 수, 상어 이동 횟수
priority[i][j][k]: i 번째 상어가 j(1~4) 방향을 바라볼 때 k(1~4) 번째 우선순위
map[][]: 상어의 위치 맵
num[][]: 지나간 상어의 넘버 맵
smell[][]: 냄새가 남은 시간 맵
sharkMap<Integer, Shark>: 상어 리스트

알고리즘

1. 상어가 있는 자리에 냄새 기록
2. 상어의 다음 자리 찾기
   2-1. 빈칸이 있으면 temp에 추가
   2-2. 빈칸이 없으면 자기 냄새가 있는 곳 temp에 추가
3. 상어 자리 옮기기
   3-1. 이미 자리 잡고 있는 상어의 숫자가 더 큰 경우 -> 내보내기
   3-2. 이미 자리 잡고 있는 상어의 숫자가 더 작은 경우 -> 자신이 나가기
4. smell 남은 시간 줄이기
   4-1. 1초 남은 자리는 삭제하기
5. 1번 상어만 남은 경우 break

상어가 지나간 자리를 어떤 자료형으로 기록해야 할지 고민이었다.
처음에는 한 칸마다 ArrayList로 정의하여 Shark가 지나갔으면 add 해주는 방식을 썼는데, 너무 복잡해졌다.
상어가 지나간 자리에 num, smell만 기록해 주면 되는 것이었으므로 2차원 배열을 사용하였더니 더 단순해졌다.

알고리즘을 풀 때 여러 가지 방법이 있지만, 그중에서 내가 헷갈리지 않고 구현하기 쉬운 자료형으로 선택해야겠다.