[BOJ-19237] 어른상어 -Java

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

19237번: 어른 상어

package 시뮬레이션;

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

public class boj_19237_어른상어 {
	static class Shark {
		int x, y, no;

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

	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static int N, M, K;
	static int sharkMap[][]; //상어의 번호를 저장하는 2차원배열
	static int smellMap[][]; //상어의 냄새를 적어주는 2차원배열 ( 0~K 까지 )
	static int sharkDir[];   //현재 상어의 방향을 저장하는 1차원배열
	static int sharkPriorityDir[][][]; //상어의 우선순위 방향을 저장 
	
	static PriorityQueue<Shark> sharkList = new PriorityQueue<>((o1, o2) -> (o2.no - o1.no)); 
	//상어의 위치,번호 저장 , 내림차순 
	static HashMap<String, Integer> smellList = new HashMap<>(); 
	//상어의 흔적 (좌표,번호) 저장 

	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());

		sharkMap = new int[N][N];
		smellMap = new int[N][N];
		sharkDir = new int[M + 1]; // 1번부터
		sharkPriorityDir = new int[M + 1][4][4];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				sharkMap[i][j] = Integer.parseInt(st.nextToken());
				if (sharkMap[i][j] != 0) {
					sharkList.add(new Shark(i, j, sharkMap[i][j])); // 상어 pq삽입
					smellMap[i][j] = K;
					smellList.put(Integer.toString(i) +","+ Integer.toString(j), sharkMap[i][j]);
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= M; i++)
			sharkDir[i] = 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++) {
					sharkPriorityDir[i][j][k] = Integer.parseInt(st.nextToken()) - 1;
				}
			}
		}

		System.out.println(solve());

	}

	private static int solve() {
		// 이동
		boolean flag=false;
		int time=-1;
		while (time<1001) {
			time++;
			int size = sharkList.size();
			if(size==1) return time;
			for (int i = 0; i < size; i++) {
				Shark shark = sharkList.poll();
				int x = shark.x;
				int y = shark.y;
				flag=false; //아무냄새 없는 방향으로 갔는지 체크 
				// 아무 냄새 없는 방향
				for (int d = 0; d < 4; d++) {
					//현재 방향 정해서 X,Y좌표 바꾸기
					int nx = x + dx[sharkPriorityDir[shark.no][sharkDir[shark.no]][d]];
					int ny = y + dy[sharkPriorityDir[shark.no][sharkDir[shark.no]][d]];

					if (nx < 0 || ny < 0 || nx >= N || ny >= N)
						continue; // 범위 벗어나면
					if (smellMap[nx][ny] != 0)
						continue; // 다른 상어냄새 있으면

					// 갈 수 있으니까 sharkMap, shrakList바꿔주기
					sharkMap[x][y] = 0;
					sharkMap[nx][ny] = shark.no;
					sharkDir[shark.no]=sharkPriorityDir[shark.no][sharkDir[shark.no]][d]; //상어방향 바꿔주기
					flag=true;
					break;
				}

				// 내 냄새로 가기 
				if(!flag) {
					for (int d = 0; d < 4; d++) {
						int nx = x + dx[sharkPriorityDir[shark.no][sharkDir[shark.no]][d]];
						int ny = y + dy[sharkPriorityDir[shark.no][sharkDir[shark.no]][d]];
						
						if (nx < 0 || ny < 0 || nx >= N || ny >= N)
							continue; // 범위 벗어나면
						if (smellList.get(Integer.toString(nx)+","+Integer.toString(ny)) != shark.no)
							continue; // 내 냄새 아니라면
						
						// 갈 수 있으니까 sharkMap, shrakList바꿔주기
						sharkMap[x][y] = 0;
						sharkMap[nx][ny] = shark.no;
						sharkDir[shark.no]=sharkPriorityDir[shark.no][sharkDir[shark.no]][d]; //상어방향 바꿔주기
						break;
					}
				}
				
			}
			// 이동 다하고 겹친거 처리해주기(함수로) + 냄새 뿌리기 
			inputSharkAndSmell();

		}
		return -1;
	}


	private static void inputSharkAndSmell() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				
				if(smellMap[i][j]!=0) { //냄새가 있다면  빼주기 
					if(--smellMap[i][j]==0) { //만약 1 뺏을 때  0 이라면 
						smellList.remove(Integer.toString(i)+","+Integer.toString(j)); //삭제 
					}
				}
				
				if(sharkMap[i][j]!=0) { //상어가 있다면  pq에 상어넣고 냄새 추가하기 
					sharkList.add(new Shark(i,j,sharkMap[i][j]));
					smellList.put(Integer.toString(i)+","+Integer.toString(j), sharkMap[i][j]);
					smellMap[i][j]=K;
				}
			}
		}
		
	}

}

 

소요시간 : 2시간 

 

1시간 30분정도에 테케를 성공시키고... 제출을 했지만.. 런타임 에러가 났습니다! 

주변 지인의 도움으로 런타임에러를 해결할 수 있었습니다.

 

 문제 풀이에 사용한 주요 변수들입니다.

 

우선 로직은 

 

1. 먼저 상어를 움직여준다 (우선순위에 따라서)

   - 만약 4방향 중 냄새가 없는 칸이 있다면 우선순위에 따라서 상어를 옮김

   - 만약 4방향 모두가 냄새가 있다면 자신의 냄새를 찾아서 움직임

 

2. sharkMap을 순회하면서 우선순위큐에 상어들의 위치 넣어주기

3. smellMap을 순회하면서 상어들의 흔적 -1 줄여주기 , 상어위치에 흔적 추가해주기 

순으로 풀었습니다.

 

상어의 흔적을 어떻게 저장할까 생각하다 HashMap<String, Integer>를 사용해서 저장했습니다
Key 값에는 좌표를 넣었습니다. 예를 들어 0,0이라면 String으로 바꾸어서 0,0을 Key 값으로 저장했습니다.
Value 값에는 상어의 번호를 넣었습니다.


런타임 에러 뜬 이유는 처음에 0,0 이면 - > 00 이런 식으로 넣어서
(1,11) (11,1) 같은 경우 모두 111로 저장해서 런타임 에러가 났습니다... 그래서 좌표 사이에,를 넣어서 저장했습니다!

삼성 시뮬레이션 문제들은 2차원 배열 맵과, list, map을 같이 들고 다니면 편한 문제가 많이 나오다 보니 문제를 풀기 전에 어떤 변수를 선언하고 들고 다녀야