[BOJ 19237] 어른상어

문제

• BOJ 19237
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

처음에 상어,좌표 각각 클래스를 만들어서 관리하려했는데 한 좌표에 여러 상어가 들어오는 경우를 처리하는데 1차 고민함..(리스트로 관리할까 했는데 상어 삭제시에 복잡해졌음) 그래서 생각을 바꿔서 좌표별 있는 상어 번호 map[][], 냄새 뿌린 상어번호 smell[][], 남은 시간 times[][] 세개의 배열을 만들어서 각각 관리해주는식으로 코드를 수정하였다.

※ 문제 읽고 도출해야할 점

• 방향정할때 어차피 우선순위대로 좌표를 정하므로 우선순위로 방향구한 후 빈칸인지 같은 냄새인지 판단한다. (처음에 문제 순서대로만 읽고 1)빈칸 2)냄새 3)1,2없으면 우선순위로 방향정하기 인줄…)
• 상어이동시에 번호가 작은 순으로 올라가므로 이미 상어가 있는 좌표에 오는 이후 상어들은 번호가 더 크므로 무조건 out. 따라서 이동과 동시에 상어를 삭제할 수 있음

1. 남은 상어 수 cnt가 1개이거나 time이 1000이상이면(-1) 종료하고 시간을 출력한다.

2. 상어를 이동시킨다.
   • 번호가 작은 순으로 sharks[]를 돌면서 상어번호 별 방향 우선순위로 다음 방향과 좌표를 구한다.
     • 먼저 빈칸이 있는 경우 이를 flag표시한다.
     • i에서 못찾았으면(flag==false) 같은 냄새인 좌표가 있는지 확인한다.
     • 찾았으면 break후 다음 좌표에 이미 상어가 존재하는지 확인한다.
       • 원래 있었던 좌표는 비워준다.
       • tmp[][]에 이미 다른 상어번호가 있으면 이 상어번호는 무조건 작기 때문에 현재 상어는 들어갈 수 없고 삭제시킨다. sharks[i]=null
       • tmp[][]가 비었으면 현재 상어를 이동시킨다.
3. 냄새를 업데이트한다.
   • map을 돌면서 tmp에 값이 있으면 현재 이동한 상어가 있으므로 그때의 상어번호를 smells[][]에, 냄새를 times[][]에 K로 업데이트한다.
   • tmp에 값이 없으면 냄새가 남아있는 경우 시간-1해주고 만약 시간이 0이면 냄새도 0으로 변경해준다.
4. time을 하나 증가시킨다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static final int N = 4;
	static int[][] dArr = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } }; //반시계방향
	static int Ans;
	
	static class Shark{
		int x, y, d, sum;
		
		public Shark(int x, int y, int d, int sum) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.sum = sum;
		}
	}
	
	static class Fish {
		int num, x, y, d;
		boolean dead;

		public Fish(int num, int x, int y, int d, boolean dead) {
			this.num = num;
			this.x = x;
			this.y = y;
			this.d = d;
			this.dead = dead;
		}
	}

	public static void main(String[] args) throws IOException {
		int[][] map = new int[N][N];
		Fish[] fishArr = new Fish[N*N+1];
		
		for (int i = 0; i < 4; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 4; j++) {
				int num = Integer.parseInt(st.nextToken()); //번호 0부터 시작
				int d = Integer.parseInt(st.nextToken()) - 1;//방향 0부터 시작
				fishArr[num] = new Fish(num, i, j, d, false);
				map[i][j] = num;
			}
		} // End input
		
		//초기 상어 세팅
		Fish f = fishArr[map[0][0]];
		Shark s = new Shark(0, 0, f.d, f.num);
		f.dead = true;
		map[0][0] = -1; //먹음 표시
		
		// 탐색 시작
		go(map, fishArr, s);
        System.out.println(Ans);
	}

	private static void go(int[][] map, Fish[] fishArr, Shark s) {
		//물고기 먹은 최대합을 답으로
		Ans = Math.max(Ans, s.sum);
		
		//1. 번호 작은 순서대로 물고기 이동
		for(int i=1; i<=N*N; i++) {
			Fish f = fishArr[i];
			if(f.dead) continue; //이미 먹은 물고기면 continue
			
			for(int d=0; d<8; d++) {
				int nd = (f.d + d) % 8;
				int nx = f.x + dArr[nd][0];
				int ny = f.y + dArr[nd][1];
				
				//범위 체크
				if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] > -1) {
					map[f.x][f.y] = 0; //현재 있던 자리는 비워줌
					
					if(map[nx][ny] == 0) { //빈칸이면 이동
						f.x = nx;
						f.y = ny;
					}else { //물고기 있으면 위치 바꿈
						Fish tmp = fishArr[map[nx][ny]];
						tmp.x = f.x;
						tmp.y = f.y;
						map[f.x][f.y] = tmp.num;
						f.x = nx;
						f.y = ny;
					}
					
					map[nx][ny] = f.num;
					f.d = nd;
					break; //이동했으면 종료
				}
			}
		}
		
		//2. 상어 이동
		for(int dist = 1; dist < N; dist++){ //최대 이동가능거리 3
			int nx = s.x + dArr[s.d][0] * dist;
			int ny = s.y + dArr[s.d][1] * dist;
			
			//범위체크, 물고기 있으면 이동 가능
			if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] > 0) {
				//배열 복사
				int[][] copyMap = copyMap(map);
				Fish[] copyFish = copyFish(fishArr);
				
				copyMap[s.x][s.y] = 0; //상어 있던곳 비움
				Fish f = copyFish[map[nx][ny]];
				Shark ns = new Shark(f.x, f.y, f.d, s.sum + f.num); //먹은 물고기 좌표,방향으로 상어상태 갱신
				f.dead = true;
				copyMap[f.x][f.y] = -1; //물고기 먹음
				go(copyMap, copyFish, ns);
			}
		}
	}

	private static Fish[] copyFish(Fish[] fishArr) {
		Fish[] tmp = new Fish[N*N+1];
		for(int i=1; i<=N*N; i++) {
			Fish f = fishArr[i];
			tmp[i] = new Fish(f.num, f.x, f.y, f.d, f.dead);
		}
		return tmp;
	}

	private static int[][] copyMap(int[][] map) {
		int[][] copy = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				copy[i][j] = map[i][j];
			}
		}
		
		return copy;
	}
}