[Java/자바 백준 19237] 어른 상어

풀이

담아야할 변수가 많기 때문에 따로 관리하는게 덜 헷갈리거라 생각했습니다.

 

사용 변수

- map : 상어 인덱스를 2차원 배열에 표현해서 실시간 위치 파악

- visited : 상어가 방문하여 해당 위치에 냄새가 있는지 파악하기 위해, 상어 인덱스와 냄새가 얼마나 남았는지 표시해주었습니다.

- priorityDir : 상어별로 우선순위 방향을 담았습니다.

- sharks : 상어의 x, y, dir(방향)을 담았습니다.

 

while문에서 시간이 1000이 초과될때까지 

- makeDir() : 우선순위에 따라 방향 이동

 

- deleteVisit() : visited에 해당 냄새 -1씩 감소

 

- moveMap() : 1번 상어부터 sharks에 x, y 값을 map 옮겨주고, 이미 map에 상어가 위치한다면 격자 밖으로 쫓아냈습니다.(상어순으로 진행하기 때문에 맵에 이미 위치한 상어는 인덱스가 낮은 값)

 

 

- makeVistit() : 이동한 상어들 해당 위치에 냄새 뿌리기

 

식으로 진행했습니다.

 

하나 참고할게 있다면 25~26%에서 틀렸다면,

시간을 1000까지 포함 안해서 틀릴 확률이 높습니다 !!(제가 그랬기때문에 ~~)

 

풀기엔 어렵지 않지만 구현은 살짝 난이도가 있는 문제였던거 같습니다~~

두시간정도 걸린 문제

package b0204;

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

public class Main_bj_g3_19237_어른상어 {
	static int N, M, K, sharkCount;
	static int[][] map;
	static int[][][] visited, priorityDir;
	static List<Shark> sharks;
	// 위 아래 왼 오 
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static private class Shark{
		int x, y, dir;
		public Shark(int x, int y, int dir) {
			this.x = x;
			this.y = y;
			this.dir = dir;
		}
	}
	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());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		// 상어 인덱스 맵 
		map = new int[N][N];
		// 상어 냄새담는 맵, 상어 인덱스와 남은 냄새크기 
		visited = new int[N][N][2];
		// 상어 x,y,dir 
		sharks = new LinkedList<>();
		for(int i = 0 ; i < M ; i++) {
			sharks.add(new Shark(-1, -1, -1));
		}
		priorityDir = new int[M][4][4];
		
		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 ) {
					// 상어 번호 
					visited[i][j][0] = map[i][j];
					visited[i][j][1] = K;
					sharks.get(map[i][j]-1).x = i;
					sharks.get(map[i][j]-1).y = j;		
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < M ; i++) {
			sharks.get(i).dir = Integer.parseInt(st.nextToken()) - 1;
		}
		
		for(int i = 0 ; i < M ; i++) {
			for(int j = 0 ; j < 4 ; j++) {
				st = new StringTokenizer(br.readLine());
				for(int k = 0 ; k < 4; k++) {					
					priorityDir[i][j][k] = Integer.parseInt(st.nextToken()) - 1;
				}
			}	
		}
		
		int time = 0;
		// 먹힌 상어 
		sharkCount = 0;
		
		while(true) {
			if(time > 1000 || sharkCount == M-1) {
				break;
			}
			
			// 우선순위 방향에 따라 상어 이동 
			makeDir();
			
			// 냄새 삭제 -1
			deleteVisit();
			
			// 이동 sharks에 따라서 map 위치 이동시키기 
			moveMap();
			
			// 이동한 위치 냄새 뿌리기 
			makeVisit();
			time ++;
		}
		if(time <= 1000) System.out.println(time);
		else System.out.println(-1);
	}
	
	private static void makeVisit() {
		for(int i = 0 ; i < M ; i++) {
			int x = sharks.get(i).x;
			int y = sharks.get(i).y;
			
			if(x == -1) continue;
			
			visited[x][y][0] = i+1;
			visited[x][y][1] = K;
		}
	}

	private static void moveMap() {
		map = new int[N][N];
		for(int i = 0 ; i < M ; i++) {
			
			int x = sharks.get(i).x;
			int y = sharks.get(i).y;
			
			if(x == -1) continue;
			
			if(map[x][y] == 0) {
				map[x][y] = i + 1;
			}
			
			else {
				sharkCount += 1;
				sharks.get(i).x = -1;
				sharks.get(i).y = -1;
				sharks.get(i).dir = -1;
			}
		}
	}

	private static void deleteVisit() {
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(visited[i][j][1] != 0) {
					visited[i][j][1] -= 1 ;
					if(visited[i][j][1] == 0) {
						visited[i][j][0] = 0;
					}
				}
			}
		}
		
	}

	private static void makeDir() {
		// 위 아래 왼 오 
		for(int i = 0 ; i < M ; i++) {
			int dir = sharks.get(i).dir;
			if(dir == -1) continue;
			boolean flag = false;
			for(int j = 0 ; j < 4 ; j++) {
				int nd = priorityDir[i][dir][j];
				int nx = sharks.get(i).x + dx[nd];
				int ny = sharks.get(i).y + dy[nd];
				if(0 > nx || nx >= N || 0 > ny || ny >= N) continue;
				// 냄새가 없는 장소가 있을시 
				if(visited[nx][ny][0] == 0) {
					flag =true;
					sharks.get(i).x = nx;
					sharks.get(i).y = ny;
					sharks.get(i).dir = nd;
					break;
				}
			}
			// 원래 자신의 냄새 자리로 돌아가기 
			if(flag == false) {
				for(int j = 0 ; j < 4 ; j++) {
					int nd = priorityDir[i][dir][j];
					int nx = sharks.get(i).x + dx[nd];
					int ny = sharks.get(i).y + dy[nd];
					if(0 > nx || nx >= N || 0 > ny || ny >= N) continue;

					if(visited[nx][ny][0] == i+1) {
						sharks.get(i).x = nx;
						sharks.get(i).y = ny;
						sharks.get(i).dir = nd;
						break;
					}
				}
			}
		}
	}

}