백준 19236 : 청소년 상어

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

19236번: 청소년 상어

[ 문제풀이 ]

상어 시리즈 2번째 문제 청소년 상어이다. 차근차근 하나씩 구현해간다면 어렵지 않게 풀 수 있을 것이다.

푸는 방법이 다양하게 존재하겠지만 나는 상어를 기준으로 물고기를 관리하는 식으로 구현하였다.

​1. 상어를 기준으로 잡고 상어 밑에서 물고기를 관리하는 맵을 만든다. 물고기를 관리하는 맵은 총 2가지로 구현하였다. 첫 번째는 1차원 배열의 fish이다. 1~16번까지의 각 물고기의 생존 여부 및 좌표와 방향을 관리하는 배열이다.

두 번째는 2차원 배열의 isFish이다. 물고기를 낮은 순번부터 이동시키기 때문에 i 번 물고기 fish[i]의 현재 위치를 빠르게 접근할 수 있도록 하기 위해서 물고기의 번호를 저장하였다.

2. 1~8 방향을 주는데 관리하기 쉽도록 -1만큼 감소시켜 0~7 방향으로 관리하자.

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

public class Main {

	static int[][] dir = {{-1,0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1, 1}};

	static class Fish {
		int y, x, direct;

		public Fish(int y, int x, int direct) {
			this.y = y;
			this.x = x;
			this.direct = direct;
		}
	}

	static class Shark {
		int y, x, direct, eat;
		int[][] isFish; //낮은 번호의 물고기부터 이동하기 위해 2차원 좌표에 물고기 위치를 저장
		Fish[] fish;

		public Shark(int y, int x, int direct, int eat) {
			this.y = y;
			this.x = x;
			this.direct = direct;
			this.eat = eat;
			isFish = new int[4][4];
			fish = new Fish[17];
		}
		
		//새로운 상어에 기존 상어의 정보(물고기 상태)를 저장
		public void init(Shark shark) {
			for (int i = 0; i < 4; ++i) {
				for (int j = 0; j < 4; ++j) {
					shark.isFish[i][j] = isFish[i][j];
				}
			}
			
			for (int i = 1; i <= 16; ++i) {
				if (fish[i] == null) continue;
				int yy = fish[i].y;
				int xx = fish[i].x;
				int dd = fish[i].direct;
				shark.fish[i] = new Fish(yy, xx, dd);
			}
		}
		
		//물고기를 자신의 방향으로 1칸 이동
		public void moveTheFish() {
			for (int i = 1; i <= 16; ++i) {
				if (fish[i] == null) continue;

				do {
					int y = fish[i].y;
					int x = fish[i].x;
					int ny = y + dir[fish[i].direct][0];
					int nx = x + dir[fish[i].direct][1];

					//범위 밖으로 넘어간다면 방향을 바꿈
					if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4) {
						fish[i].direct = (fish[i].direct + 1) % 8;
						continue;
					}

					//상어가 존재한다면 방향을 바꿈
					if (ny == this.y && nx == this.x) {
						fish[i].direct = (fish[i].direct + 1) % 8;
						continue;
					}

					//빈칸(물고기 x)이면 1칸 이동
					if (isFish[ny][nx] == 0) {
						isFish[ny][nx] = isFish[y][x];
						fish[i].y = ny;
						fish[i].x = nx;
						isFish[y][x] = 0;
						break;
					}

					//물고기가 존재한다면 위치를 서로 바꿈
					int k = isFish[ny][nx];
					fish[i].y = ny;
					fish[i].x = nx;
					fish[k].y = y;
					fish[k].x = x;
					isFish[ny][nx] = i;
					isFish[y][x] = k;
					break;
				} while(true);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		Shark shark = null;

		for (int i = 0; i < 4; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; ++j) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken()) - 1;

				if (i == 0 && j == 0) {
					shark = new Shark(i, j, b, a);
				} else {
					shark.isFish[i][j] = a;
					shark.fish[a] = new Fish(i, j, b);
				}
			}
		}

		int answer = 0;
		Queue<Shark> q = new LinkedList<>();
		q.offer(shark);
		
		while (!q.isEmpty()) {
			Shark sh = q.poll();
			answer = Math.max(answer, sh.eat);
			
			//1번부터 16번까지 살아있는 물고를기 1칸 이동
			sh.moveTheFish();
	
			int y = sh.y;
			int x = sh.x;
			//상어의 방향으로 못움직일때까지 1칸씩 움직이면서 갈 수 있는 위치에 새로운 상어를 생성
			while (true) {
				y += dir[sh.direct][0];
				x += dir[sh.direct][1];
				
				if (y < 0 || x < 0 || y >= 4 || x >= 4) break;
				if (sh.isFish[y][x] == 0) continue;
				
				Shark nsh = new Shark(y, x, sh.fish[sh.isFish[y][x]].direct, sh.eat + sh.isFish[y][x]);
                //기존 상어의 정보를 저장
				sh.init(nsh);
                //새로운 상어가 잡아먹은 물고기를 제거
				nsh.fish[sh.isFish[y][x]] = null;
				nsh.isFish[y][x] = 0;
				q.offer(nsh);
			}
		}
		bw.write(answer + "\n");
		bw.flush(); bw.close(); br.close();
	}
}