백준 19237 : 어른 상어

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

19237번: 어른 상어

[ 문제풀이 ]

삼성 문제들은 대부분 완전 탐색 기반으로 지문에 나오는 조건을 완벽하게 구현한다면 웬만하면 정답을 맞힐 수 있는 형태이다. 이 문제 또한 주어진 지문을 토대로 총 4단계 과정으로 세분화할 수 있다.

1. 상어를 자신의 이동 방향으로 1칸 이동시킨다.
2. 모든 냄새를 감소시킨다.
3. 같은 위치에 상어가 여러 마리가 존재한다면 가장 작은 번호를 가진 상어를 제외하고 모두 제거한다.
4. 남아있는 상어들의 위치에 각자 냄새를 뿌린다.

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

public class Main {

	static int n, m, k, cnt;
	static int[][] map;
	static int[][] allSmell;
	static int[][][] smell;
	static Shark[] shark;
	static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
	
	static class Shark {
		int y, x, idx, direct;
		int[][] priorityDirect = new int[4][4];

		Shark(int y, int x, int idx, int direct){
			this.y = y;
			this.x = x;
			this.idx = idx;
			this.direct = direct;
		}

		public void move() {
			boolean find = false;
			
			//상어의 우선순위에 따라 4방향을 돌며 냄새가 없는 칸을 찾는다. 
			for (int i = 0; i < 4; ++i) {
				int ny = y + dir[priorityDirect[direct][i]][0];
				int nx = x + dir[priorityDirect[direct][i]][1];

				if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
				if (allSmell[ny][nx] > 0) continue;
				direct = priorityDirect[direct][i];
				y = ny;
				x = nx;
				find = true;
				break;
			}
			
			//냄새없는 칸을 찾지 못했다면, 자신의 냄새가 있는 칸을 찾는다.
			if (!find) {
				for (int i = 0; i < 4; ++i) {
					int ny = y + dir[priorityDirect[direct][i]][0];
					int nx = x + dir[priorityDirect[direct][i]][1];

					if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
					if (smell[idx][ny][nx] == 0) continue;
					direct = priorityDirect[direct][i];
					y = ny;
					x = nx;
					break;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		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());
		int time = 0;
		shark = new Shark[m+1];
		map = new int[n][n];
		allSmell = new int[n][n];
		smell = new int[m+1][n][n];
		cnt = m;
		for (int i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] != 0) {
					shark[map[i][j]] = new Shark(i, j, map[i][j], -1);
					smell[map[i][j]][i][j] = k;
					allSmell[i][j] = k;
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= m; ++i) {
			shark[i].direct = Integer.parseInt(st.nextToken()) - 1;
		}
		
		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) {
					shark[i].priorityDirect[j][k] = Integer.parseInt(st.nextToken()) - 1;	
				}
			}
		}
		
		while (cnt > 1 && time <= 1000) {
			time++;
			//1. 상어를 자신의 이동 방향으로 1칸 이동시킨다.
			for (int i = 1; i <= m; ++i) {
				if (shark[i] == null) continue;
				shark[i].move();
			}
			//2. 모든 냄새를 감소시킨다.
			decreaseSmell();
			//3. 같은 위치에 상어가 여러마리가 존재한다면 가장 작은 번호를 가진 상어를 제외하고 모두 제거한다.
			removeShark();
			//4. 남아있는 상어들의 위치에 각자 냄새를 뿌린다.
			spreadSmell();
		}
		bw.write((time > 1000 ? -1 : time) + "\n");
		bw.flush();bw.close();br.close();
	}
	
	public static void spreadSmell() {
		for (int i = 1; i <= m; ++i) {
			if (shark[i] == null) continue;
			int y = shark[i].y;
			int x = shark[i].x;
			allSmell[y][x] = k;
			smell[i][y][x] = k;
		}
	}
	
	public static void removeShark() {
		for (int i = 1; i <= m-1; ++i) {
			if (shark[i] == null) continue;
			for (int j = i+1; j <= m; ++j) {
				if (shark[j] == null) continue;
				if (shark[i].y == shark[j].y && shark[i].x == shark[j].x) {
					cnt--;
					shark[j] = null;
				}
			}
		}
	}

	public static void decreaseSmell() {
		for (int k = 1; k <= m; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (smell[k][i][j] > 0) {
						smell[k][i][j]--;
						allSmell[i][j]--;
					}
				}
			}
		}
	}
}