[백준 - Java] 19236번 : 청소년 상어 (삼성 SW 역량 테스트 기출 문제)

문제

www.acmicpc.net/problem/19236

19236번: 청소년 상어

공간과 물고기 표현 

상어가 이동하며 먹을 수 있는 물고기 번호의 합의 최댓값을 구하는 문제이다.

조건에 따라 구현해보자.

 

 

• 4 ×4 크기의 공간이 있고, 크기가 1 ×1인 정사각형 칸으로 나누어져 있다.

• 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다.

-> 이차원 배열을 map을 만들어 공간을 나타낸다.

 

-> map에는 물고기의 번호가 저장된다. (1 <= 물고기 번호 <= 16)

 

-> 현재 상어가 있는 칸 : -1

 

-> 상어도 물고기도 없는 빈 칸 : 0

 

int[][] map = new int[4][4]; //4x4 공간을 나타내는 map 배열 

 

• 한 칸에는 물고기가 한 마리 존재한다.

• 각 물고기는 번호와 방향을 가지고 있다.

• 1 <= 번호 <= 16 (중복 X)

• 방향은 8가지 방향 중 하나이고, 1 ~8 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미

-> Fish 클래스를 만들어 물고기의 정보를 관리하도록 했다.

 

-> 상어한테 먹혀 없어지는 물고기가 있기 때문에, 추가로 alive 변수를 만들어 0일 땐 죽은 물고기, 1일 땐 살아있는 물고기를 나타냄

 

class Fish {
	int num; // 물고기 번호 
	int x; // x 위치
	int y; //y 위치
	int dir; // 방향
	int alive; //죽었는지 살았는지 판별을 위한 변수 - 0 죽음, 1 살아있음 

	Fish(int num, int x, int y, int dir, int alive) {
		this.num = num;
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.alive = alive;
	}
}

 

공간과 물고기를 표현했다면 본격적으로 상어가 물고기를 잡아먹고 이동하는 과정을 구현해보자.

상어 이동 과정

1. 시작 -> 물고기 먹음

처음 시작하면 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다.

상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다.

2. 물고기 이동

이후 물고기가 이동한다.

 

• 물고기는 번호가 작은 물고기부터 순서대로 이동한다.

• 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.

• 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.

• 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.

• 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

3. 상어 이동

물고기의 이동이 모두 끝나면 상어가 이동한다.

 

• 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다.

• 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.

• 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.

• 물고기가 없는 칸으로는 이동할 수 없다.

• 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.

 

상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

요약

이렇듯 처음 상어가 (0, 0) 부터 시작해 그 칸의 물고기를 잡아먹고 방향을 가진다.

 

이후 물고기가 이동하고, 다시 상어가 이동하고, 다시 물고기를 잡아먹고 이 과정이 계속해서 반복된다.

 

그리고 상어가 이동할 때, 상어는 상어의 방향 내에서 이동할 수 있는 칸 중 하나로 이동한다.

 

이 과정이 계속 반복되며 상어가 먹은 물고기 번호의 합의 최댓값을 출력해야 한다.

 

-> 즉, 상어가 어느 칸을 선택해 이동하느냐에 따라 여러 가지 경우의 수가 발생한다.

 

-> 상어가 움직인 여러 경우의 수를 다 따져보아 가장 최대로 물고기를 먹은 경우를 구해 그 총합을 구해야 한다.

 

-> 그러기 위해 모든 경우를 탐색해보는 완전 탐색 기법 중 하나인 DFS 깊이 우선 탐색을 이용해 구현한다.

구현

먼저 입력을 받아 물고기의 정보를 저장하고 이를 바탕으로 map을 구성해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다.

물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다.

방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

 

-> 방향의 경우 쉽게 변경해주기 위해 dx, dy 배열을 만들었다.

 

왜? 방향 바꾸기 팁!

2차원 배열에서 상 하 좌 우 이동해야 하는 경우가 알고리즘 문제에서 종종 나온다.

이때 x, y 이동을 편리하게 하기 위해 dx, dy 배열을 만들어 두면 좋다.

 

 

인덱스 0, 1, 2, 3의 순으로 상, 좌, 하, 우라고 외우면 좋다.

위의 그림에서 상은 (-1, 0)부터 시작하고 반시계 방향으로 우까지 돌아가는 순이다.

이를 배열로 나타내면 아래와 같다. 

 

 

 

예를 들어 현재 2차원 배열의 (2, 2)에 상어가 있다.

여기서 위쪽으로 가려면 (2, 2) + (-1, 0) => (1, 2)

왼쪽은 (2, 2) + (0, -1) => (2, 1)

아래쪽은 (2, 2) + (1, 0) => (3, 2)

오른쪽은 (2, 2) + (0, 1) => (2, 3) 

이런 식으로 dx, dy의 방향에 따른 인덱스 값을 현재 좌표 값에 더해서 위치를 간단히 이동시킬 수 있다!

 

↑, ↖, ←, ↙, ↓, ↘, →, ↗  상, 상좌, 좌, 좌하, 하, 하우, 우, 상우 순서로 아래와 같이 dx, dy배열을 구성했다.

 

public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //상, 상좌, 좌, 좌하, 하, 하우, 우, 상우 순서 
public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};

 

public class Main {
	public static int[][] map; //전체 맵 
	public static Fish[] fish; //물고기 정보 저장 
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //상, 상좌, 좌, 좌하, 하, 하우, 우, 상우
	public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
	public static int ans = 0; //정답 담을 변수 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		map = new int[4][4];
		fish = new Fish[17];
		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부터 시작하기 때문에 -1 (0~7)
				int dir = Integer.parseInt(st.nextToken())-1;

				// 물고기 배열에 저장 - 번호, x좌표, y좌표, 방향, 생사 여부(초반엔 다 살아있음 1)
				fish[num] = new Fish(num, i, j, dir, 1); 

				// map에 물고기 번호 저장 
				map[i][j] = num;
			}
		}
	}
}

 

1. 시작 -> 물고기 먹음

처음 시작하면 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다.

상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다.

 

-> 상어의 위치를 0, 0으로 만들어주고, 방향을 가진다.

-> (0, 0) 위치에 있던 물고기 죽인 뒤 먹은 물고기 합을 구할 변수 eat에 넣어준다.

-> 상어가 있는 위치는 -1로 바꾸어 준다.

 

int sx = 0, sy = 0; //상어의 위치
int sd = fish[map[0][0]].dir; //초기 상어의 방향 
int eat = map[0][0]; // 먹은 물고기 번호 합 저장 변수 - (0, 0) 물고기 먹음 
fish[map[0][0]].alive = 0; //(0, 0) 물고기 죽음
map[0][0] = -1; //상어가 있는 위치 -1 

 

DFS

상어는 이동할 수 있는 여러 칸(4*4 배열이니 최대 3개의 칸) 중에서 하나의 칸을 선택해 움직인다.

칸을 이동하며 먹을 수 있는 최대 물고기 번호합을 구하기 위해 DFS를 통해 모든 상어의 경로를 구해보며 물고기를 먹어본다.

DFS를 수행하며 상어가 이동하고, 물고기가 이동하는 과정을 진행된다.

DFS 함수는 상어의 현재 x좌표, 상어의 현재 y좌표, 상어의 현재 진행 방향, 현재까지 먹은 물고기 번호의 합을 나타내는 4개의 인자를 가진다.

 

dfs(sx, sy, sd, eat);

////

public static void dfs(int sx, int sy, int sd, int eat) {
	ans = Math.max(ans, eat); //이전에 먹었던 물고기 번호 합 max 비교해 ans에 저장 
}

 

DFS를 돌면서 물고기 번호 합의 최댓값을 구하기 위해

정답 변수에 Math.max로 경로마다 구해졌던 eat값 중 큰 값이 ans 변수에 저장된다.

 

여기서 잠깐!

무작정 DFS를 돌리면 원하는 결과를 얻을 수 없다.

 

DFS를 돌면서 물고기가 이동하고, 상어가 이동한다.

이 과정에서 맵의 물고기와 상어의 위치가 변경된다.

또한 물고기의 상태 역시 살았느냐 죽었느냐로 바뀌게 된다.

 

DFS는 재귀를 통해 진행되기 때문에, 한 경우를 체크하고 그다음 경우를 체크하기 위해서 실행했던 내용을 취소함으로써 되돌려 놓는 과정이 필요하다.

즉, 맵과 물고기의 상태를 기억해 놓고, 다시 이전의 상태로 되돌려 놓는 과정이 필요하다.

 

ex) 상어가 1번 물고기를 먹었다.

1번 물고기는 죽은 상태로 다른 물고기들은 이동하고, 상어 역시 이동한다. (상어가 물고기 먹고 -> 물고기 이동 -> 상어 이동 반복)

1번 물고기를 먹은 경우의 수를 재귀를 통해 모두 훑어본 뒤, 2번 물고기를 먹은 경우의 수를 진행한다.

이때 이미 1번 물고기 경우의 수를 알아보는 과정에서 물고기들이 다 이동해 초반의 맵 상태를 잃었고, 1번 물고기 역시 죽은 상태이다.

 

그래서 상어가 물고기를 먹기 전의 맵의 상태, 물고기의 상태를 기억해 놓고 경우마다 기억했던 상태를 다시 되돌려 주는 과정이 필요하다.

(같은 말 = 경우마다 어떤 물고기가 먹혔는지, 그때의 맵은 어떠했는지 기억해 놓고, 다른 물고기를 먹는 경우에는 이전 경우에서 기억한 물고기와 맵의 상태를 되돌려 주어야 한다는 것)

 

-> DFS 내에서 맵과 물고기의 상태를 복사해 놓는다.

 

public static void dfs(int sx, int sy, int sd, int eat) {
	//map 배열 복사 - 기존 map 유지를 위해 복사 
	int[][] tempMap = new int[map.length][map.length];
	for(int i = 0; i < map.length; i++) {
		System.arraycopy(map[i], 0, tempMap[i], 0, map.length);
	}

	//fish 배열 복사 
	Fish[] tempFish = new Fish[fish.length];
	for(int i=1; i<=16; i++) 
		tempFish[i] = new Fish(fish[i].num, fish[i].x, fish[i].y, fish[i].dir, fish[i].alive);
}

 

배열 복사 주의!

자바에서 객체를 복사하는 경우에는 얕은 복사와 깊은 복사 2가지가 있다.

 

얕은 복사는 단순히 객체의 주소 값만을 복사하는 것으로 실제로는 하나의 주소 값을 가지고 있으므로 하나라고 볼 수 있다.

즉 복사된 배열이나 원본 배열이 변경될 때 서로 같이 값이 같이 변경된다.

 

깊은 복사의 경우 실제 객체를 복사하는 것으로 복사된 배열이나 원본 배열이 변경될 때 서로 간의 값은 변경되지 않는다.

 

배열 복사와 관련된 유용한 포스트를 추천합니다!

 

[Java] 자바 배열을 복사하는 다양한 방법 (깊은 복사, 얕은 복사)

 

따라서 map과 fish 배열을 복사하는 경우 깊은 복사를 통해 값을 복사해주는 것을 유의해야 한다.

 

map배열의 경우 2차원 배열이기 때문에 arraycopy() 메서드를 이용해 배열을 복사해주었다.

 

fish 배열의 경우 1차원 배열을 깊은 복사하는 메소드를 사용하면 안 됨. 그래서 for문을 이용해 일일이 값을 옮겨 주었다.

왜냐하면 fish 배열의 경우 Fish 클래스 객체를 담는 배열이기 때문에 new를 이용해 객체를 생성해주어야 한다.

(뭐 tempFish [i] = new Fish(0, 0, 0, 0, 1); 이렇게 객체 초기화를 한 뒤 깊은 복사 메서드를 사용해도 무방)

 

* 아래는 잘못된 코드의 예시

 

int[][] tempMap = map; // X
int[][] tempMap = map.clone(); // X

Fish[] tempFish = fish.clone(); // X
Fish[] tempFish = Arrays.copyOf(fish, fish.length); // X
Fish[] tempFish = new Fish[fish.length]; // X
System.arraycopy(fish, 0, tempFish, 0, fish.length); // X

 

2. 물고기 이동

따로 moveFish() 함수를 만들어 구현했다. 

• 물고기는 번호가 작은 물고기부터 순서대로 이동한다.

• 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.

• 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.

• 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.

• 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

-> 죽은 물고기라면 패스하고 번호가 작은 순서부터 큰 순서까지 fish 배열 안의 물고기들을 for문에서 하나하나 움직인다.

 

-> 처음엔 물고기가 원래 가진 방향부터 총 8방향을 검증한다. 

-> 방향에 맞게 좌표를 이동하며 새로운 방향으로 이동할 수 있는지를 검증한다. (이동할 수 없다면 방향 회전 dir++)

-> 만약 새로운 방향이 8방향을 넘어갈 경우를 대비해 방향은 dir %= 8 나머지 연산을 해준다.

-> 새로운 위치에 상어가 없고 경계를 넘지 않는다면 이동할 수 있다.

-> 새로운 위치에 물고기가 없다면 바로 넣어주고, 있다면 둘의 위치를 바꾸어준다.

 

public static void moveFish() {
	for(int i = 1; i < 17; i++) { //i는 현재 물고기의 번호 
		if(fish[i].alive == 0) { //죽은 물고기라면 넘김 
			continue;
		}

		int cnt = 0;
		int dir = fish[i].dir;//현재 i번째 물고기의 방향 
		int nx = 0, ny = 0; //물고기가 이동할 칸의 x, y값 

		while(cnt < 8) { //이동할 수 있는 위치를 찾을때까지 45도 방향 바꾸며 반복 
			dir %= 8; //방향 +1로 범위 넘어가는 걸 처리하기 위한 나머지 연산 
			fish[i].dir = dir; //방향 바꿨다면 바뀐 것 적용 

			nx = fish[i].x + dx[dir]; //방향에 맞게 좌표 이동 
			ny = fish[i].y + dy[dir];

			//이동할 위치에 상어가 없고, 경계를 넘지 않는다면 이동 가능 
			if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny] != -1) { 
				if(map[nx][ny] == 0) { //이동할 위치가 빈칸일 경우 
					map[fish[i].x][fish[i].y] = 0; //기존 위치 빈칸으로 
					fish[i].x = nx;
					fish[i].y = ny;
					map[nx][ny] = i; 
				} else { //이동할 위치에 다른 물고기가 있을 경우 
					// 바꿀 물고기 위치 변경 
					int changeFish = fish[map[nx][ny]].num;
					fish[changeFish].x = fish[i].x;
					fish[changeFish].y = fish[i].y;
					map[fish[changeFish].x][fish[changeFish].y] = changeFish;

					//현재 물고기 위치 변경 
					fish[i].x = nx;
					fish[i].y = ny;
					map[nx][ny] = i;
				}
				break;
			} else {
				dir++;
				cnt++;
			}
		}
	}
}

 

3. 상어 이동

물고기의 이동이 모두 끝나면 상어가 이동한다.

 

• 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다.

• 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.

• 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.

• 물고기가 없는 칸으로는 이동할 수 없다.

• 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.

-> 맵은 4 * 4 크기로 고정되어 있기 때문에 어느 위치에 있던지 최대 3번만 움직일 수 있다.

-> 따라서 for문을 통해 방향에 맞는 새로운 칸으로 총 3번 움직여준다.

 

-> 이동한 칸에 물고기가 있다면 상어는 물고기를 먹고 방향을 가진다. 그리고 물고기는 죽은 상태가 된다.

-> 그리고 이동한 새로운 칸에서부터 다시 DFS를 수행한다.

-> DFS를 끝내고 돌아온 후에는, 다음 DFS를 위해 상어가 먹었던 물고기를 살리고, 둘의 위치를 원래대로 되돌려 놓는다.

 

-> 마지막으로 tempMap과 tempFish에 저장된 값으로 맵과 물고기의 상태를 원래대로 되돌려 놓는다.

    (DFS 경우마다 물고기를 이동시켜 맵이 바뀌었기 때문)

 

public static void dfs(int sx, int sy, int sd, int eat) {
	ans = Math.max(ans, eat); //이전에 먹었던 물고기 번호 합 max 비교해 ans에 저장 

	//map 배열 복사
	int[][] tempMap = new int[map.length][map.length];
	for(int i = 0; i < map.length; i++) {
		System.arraycopy(map[i], 0, tempMap[i], 0, map.length);
	}

	//fish 배열 복사 
	Fish[] tempFish = new Fish[fish.length];
	for(int i = 1; i <= 16; i++) 
		tempFish[i] = new Fish(fish[i].num, fish[i].x, fish[i].y, fish[i].dir, fish[i].alive);	

	// 물고기 이동 
	moveFish();

	// 상어 이동 
	for(int i = 1; i < 4; i++) { //4*4 행렬로 1칸, 2칸, 3칸까지 최대로 이동 가능
		int nx = sx + dx[sd] * i;
		int ny = sy + dy[sd] * i;

		//경계를 벗어나지 않고, 물고기가 없는 빈칸이 아닐 경우 
		if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny] != 0) { 
			int eatFish = map[nx][ny];
			int nd = fish[eatFish].dir;
			map[sx][sy] = 0;
			map[nx][ny] = -1;
			fish[eatFish].alive = 0;

			dfs(nx, ny, nd, eat+eatFish);

			fish[eatFish].alive = 1; // 물고기 상태, 상어의 위치 원래대로 되돌리기 
			map[sx][sy] = -1;
			map[nx][ny] = eatFish;
		}
	}

	// 맵 상태, 물고기 정보 되돌리기 
	for(int j = 0; j < map.length; j++)
		System.arraycopy(tempMap[j], 0, map[j], 0, map.length);

	for(int i=1; i<=16; i++)
		fish[i] = new Fish(tempFish[i].num, tempFish[i].x, tempFish[i].y, tempFish[i].dir, tempFish[i].alive);
}

전체 코드

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

public class Main {
	public static int[][] map; //전체 맵 
	public static Fish[] fish; //물고기 정보 저장 
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //상, 상좌, 좌, 좌하, 하, 하우, 우, 상우
	public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
	public static int ans = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		map = new int[4][4];
		fish = new Fish[17];
		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()); // 물고기 번호 
				int dir = Integer.parseInt(st.nextToken())-1; // 물고기 방향
				fish[num] = new Fish(num, i, j, dir, 1); 
				map[i][j] = num; //map에 물고기 번호 저장 
			}
		}

		int sx = 0, sy = 0; //상어의 위치
		int sd = fish[map[0][0]].dir; //초기 상어의 방향 
		int eat = map[0][0]; // 먹은 물고기 번호 합 저장 변수 - (0, 0) 물고기 먹음 
		fish[map[0][0]].alive = 0; //(0, 0) 물고기 죽음	
		map[0][0] = -1; //상어가 있는 위치 -1 

		dfs(sx, sy, sd, eat);

		System.out.println(ans);
	}

	public static void dfs(int sx, int sy, int sd, int eat) {
		ans = Math.max(ans, eat); //이전에 먹었던 물고기 번호 합 max 비교해 ans에 저장 

		//map 배열 복사
		int[][] tempMap = new int[map.length][map.length];
		for(int i = 0; i < map.length; i++) {
			System.arraycopy(map[i], 0, tempMap[i], 0, map.length);
		}

		//fish 배열 복사 
		Fish[] tempFish = new Fish[fish.length];
		for(int i = 1; i <= 16; i++) 
			tempFish[i] = new Fish(fish[i].num, fish[i].x, fish[i].y, fish[i].dir, fish[i].alive);

		// 물고기 이동 
		moveFish();

		// 상어 이동 
		for(int i = 1; i < 4; i++) { //4*4 행렬로 1칸, 2칸, 3칸까지 최대로 이동 가능
			int nx = sx + dx[sd] * i;
			int ny = sy + dy[sd] * i;

			//경계를 벗어나지 않고, 물고기가 없는 빈칸이 아닐 경우 
			if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny] != 0) { 
				int eatFish = map[nx][ny];
				int nd = fish[eatFish].dir;
				map[sx][sy] = 0;
				map[nx][ny] = -1;
				fish[eatFish].alive = 0;

				dfs(nx, ny, nd, eat+eatFish);

				fish[eatFish].alive = 1; // 물고기 상태, 상어의 위치 원래대로 되돌리기 
				map[sx][sy] = -1;
				map[nx][ny] = eatFish;
			}
		}

		// 맵 상태, 물고기 정보 되돌리기 
		for(int j = 0; j < map.length; j++) 
			System.arraycopy(tempMap[j], 0, map[j], 0, map.length);

		for(int i=1; i<=16; i++)
			fish[i] = new Fish(tempFish[i].num, tempFish[i].x, tempFish[i].y, tempFish[i].dir, tempFish[i].alive);
	}

	//물고기 이동 
	public static void moveFish() {
		for(int i = 1; i < 17; i++) { //i는 현재 물고기의 번호 
			if(fish[i].alive == 0) { //죽은 물고기라면 넘김 
				continue;
			}

			int cnt = 0;
			int dir = fish[i].dir;//현재 i번째 물고기의 방향 
			int nx = 0, ny = 0; //물고기가 이동할 칸의 x, y값 

			while(cnt < 8) { //이동할 수 있는 위치를 찾을때까지 45도 방향 바꾸며 반복 
				dir %= 8; //방향 +1로 범위 넘어가는 걸 처리하기 위한 나머지 연산 
				fish[i].dir = dir; //방향 바꿨다면 바뀐 것 적용 

				nx = fish[i].x + dx[dir]; //방향에 맞게 좌표 이동 
				ny = fish[i].y + dy[dir];

				//이동할 위치에 상어가 없고, 경계를 넘지 않는다면 이동 가능 
				if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny] != -1) { 
					if(map[nx][ny] == 0) { //이동할 위치가 빈칸일 경우 
						map[fish[i].x][fish[i].y] = 0; //기존 위치 빈칸으로 
						fish[i].x = nx;
						fish[i].y = ny;
						map[nx][ny] = i; 
					} else { //이동할 위치에 다른 물고기가 있을 경우 
						// 바꿀 물고기 위치 변경 
						int changeFish = fish[map[nx][ny]].num;
						fish[changeFish].x = fish[i].x;
						fish[changeFish].y = fish[i].y;
						map[fish[changeFish].x][fish[changeFish].y] = changeFish;

						//현재 물고기 위치 변경 
						fish[i].x = nx;
						fish[i].y = ny;
						map[nx][ny] = i;
					}
					break;
				} else {
					dir++;
					cnt++;
				}
			}
		}
	}

}

class Fish {
	int num;
	int x;
	int y;
	int dir;
	int alive; //0 죽음, 1 살아있음 

	Fish(int num, int x, int y, int dir, int alive) {
		this.num = num;
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.alive = alive;
	}
}

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%2319236/src

KwonMinha/BOJ