[JAVA] BOJ_19236. 청소년 상어

🐒 문제

19236번: 청소년 상어

문제가 너무 길어서 윗부분만,,

---

🐈 풀이 

1. 어떤 결과값을 도출해야 할까?

상어가 움직일 수 있는 모든 경우의 수를 고려하여, 먹을 수 있는 물고기 번호의 합의 최댓값을 구해야 한다.모든 경우의 수를 고려함을 보아 백트래킹 알고리즘을 통한 접근이 필요할 수 있음을 알 수 있다.

 

2. 어떻게 도출해낼까?

주어진 문제의 흐름을 따라가보면, [물고기의 이동 -> 상어의 이동] 이 계속해서 반복한다.

따라서, 우리는 물고기의 이동과 상어의 이동을 구현해야한다.

위 사항들을 구현하기 위해 3차원 배열과 HashMap을 도구로 사용했다.

 

- 3차원 배열 : 물고기의 번호, 방향 저장

- HashMap : 물고기의 번호를 key로, 물고기의 좌표를 저장

 

물고기, 상어의 이동을 구현할 때 위 두가지 도구들을 갱신해주면서 풀이해 나갔다.

 

1) 물고기의 이동

 - 물고기가 바라보고 있는 방향으로 한 칸 이동한다.

   - 이동 방식은 이동할 위치에 있는 물고기와 자리를 바꾸는 방식이다.

   - 이동할 위치에 물고기가 없다면, 현재 물고기만 이동시켜주면 된다.

=> 3차원 배열의 자리바꿈, HashMap value값 변경을 통해 구현

 

- 물고기가 바라보고 있는 방향이 배열의 끝이거나 상어라면?

   - 반시계 방향으로 45도 방향을 바꾼다.

=> 8방향 델타배열을 통해 구현

 

2) 상어의 이동

- 상어가 바라보고 있는 방향에 물고기가 있다면, 해당 위치로 이동한다.

   - 물고기의 움직임과는 차이가 있는데, 물고기는 단 한 칸만 이동할 수 있다면, 상어는 맵의 끝까지 이동할 수 있다.

   - 위 사진처럼 상어가 [0, 0]에 위치하고 있고 우하단을 바라보고 있다면, 1칸 ~ 3칸의 범위 내에서 이동할 수 있다.

- 상어가 바라보고 있는 방향에 물고기가 없다면, 더 이상 이동하지 못한다.

=> 백트래킹과 동시에 3차원 배열, HashMap의 갱신을 통해 구현

 

3. 특별히 고려해야 할 사항은?

1) 상어는 1칸 ~ 3칸의 범위 내에서 이동할 수 있다.

   - 이 부분을 백트래킹을 통해 구현해줘야 한다. 1칸을 이동한 경우에서부터 끝까지,, 2칸을 이동한 경우에서부터 끝까지,,

2) 상어가 이동하는 모든 경우를 고려하기 위해, 물고기와 상어의 상태를 저장해 둔 3차원 배열은 어떻게 처리해줘야하나?

   - 상어의 이동이 발생할 때 마다 기존의 3차원 배열을 복사해서 사용한다. 이렇게 되면 다른 경우의 수를 고려할 때 3차원 배열이 망가져있는 경우가 발생하지 않는다.

---

🐕‍🦺 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	static int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dc = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int max;

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

		// map[r][c][0] = 물고기 번호
		// map[r][c][1] = 물고기 방향
		int[][][] map = new int[4][4][2];
		
		// HashMap<물고기번호, 물고기좌표>
		HashMap<Integer, int[]> pos = new HashMap<>();

		// 물고기 정보 입력받기
		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을 빼서 저장한다.
				int dir = Integer.parseInt(st.nextToken(" ")) - 1;
				
				// 배열에 물고기 번호, 방향 저장
				map[i][j] = new int[] { num, dir };
				
				// HashMap에 (물고기 번호 : 물고기 좌표) 저장
				pos.put(num, new int[] { i, j });
			}
		}
		// map[i][j][0] = -1 : 상어
		// map[i][j][0] = 0 : 빈공간

		//// 상어 초기 설정

		// 첫 위치에 있는 물고기 제거
		pos.remove(map[0][0][0]);

		// 상어의 위치 저장
		pos.put(-1, new int[] { 0, 0 });

		// 초기 점수
		int initScore = map[0][0][0];

		// 해당 위치를 상어로 만든다
		map[0][0][0] = -1;

		// 물고기 이동
		fishMove(map, pos, initScore);

		System.out.println(max);
	}

	static void fishMove(int[][][] map, HashMap<Integer, int[]> pos, int score) {

		// 물고기 자리 이동
		for (int i = 1; i <= 16; i++) {

			// 해당 번호의 물고기가 없다면(이미 잡아먹혔다면) 넘기기
			if (pos.get(i) == null) {
				continue;
			}

			// 물고기의 위치 r, c
			int r = pos.get(i)[0];
			int c = pos.get(i)[1];

			// 받아온 물고기가 상어나 빈 공간이 아니라면
			if (map[r][c][0] != 0 && map[r][c][0] != -1) {

				// 현재 물고기가 이동 가능한 경로를 8방 탐색
				for (int k = 0; k < 8; k++) {
					int nr = r + dr[map[r][c][1]];
					int nc = c + dc[map[r][c][1]];

					// 다음 좌표가 배열을 벗어나지 않고, 상어가 아닐 때
					if (nr >= 0 && nc >= 0 && nr < 4 && nc < 4 && map[nr][nc][0] != -1) {

						//// 1. 자리 바꾸기 (HashMap 갱신)

						// 현재 물고기의 자리를 새롭게 갱신
						pos.put(map[r][c][0], new int[] { nr, nc });

						// 물고기의 다음 이동장소가 빈 공간이 아닐때만
						if (map[nr][nc][0] != 0) {

							// 해당 물고기의 위치도 바꿔준다
							pos.put(map[nr][nc][0], new int[] { r, c });
						}

						//// 2. 자리 바꾸기 (배열 갱신)
						int[] tmp = map[r][c];
						map[r][c] = map[nr][nc];
						map[nr][nc] = tmp;

						break;
					} else {

						// 물고기 방향 바꾸기
						map[r][c][1] = (map[r][c][1] + 1) % 8;
					}
				}
			}
		}

		sharkMove(map, pos, score);
	}

	static void sharkMove(int[][][] map, HashMap<Integer, int[]> cpos, int score) {

		// 점수 갱신
		if (score > max) {
			max = score;
		}

		// 상어의 위치 r, c
		int[] shark = cpos.get(-1);
		int r = shark[0];
		int c = shark[1];

		// 상어는 현재 맵에서 최대 3칸까지 이동 가능. 이동가능한 다음 좌표 탐색
		for (int i = 1; i <= 3; i++) {
			int nr = r + dr[map[r][c][1]] * i;
			int nc = c + dc[map[r][c][1]] * i;

			// 다음 이동위치가 배열을 벗어나지 않고, 빈 공간이 아니라면
			if (nr >= 0 && nc >= 0 && nr < 4 && nc < 4 && map[nr][nc][0] != 0) {

				//// 백트래킹을 위한 준비과정 - 현재의 상태를 기억해둬야 한다.

				// 물고기별 좌표를 담고있는 HashMap 복사
				HashMap<Integer, int[]> pos = (HashMap<Integer, int[]>) cpos.clone();

				// 현재 HashMap 복사
				int[][][] copyMap = new int[4][4][2];

				for (int k = 0; k < 4; k++) {
					for (int j = 0; j < 4; j++) {
						copyMap[k][j] = map[k][j].clone();
					}
				}

				// 이동할 좌표에 있는 물고기의 번호(점수)
				int fish = copyMap[nr][nc][0];

				//// 상어 이동시키기

				// 1. HashMap 갱신
				pos.remove(copyMap[nr][nc][0]);
				pos.put(-1, new int[] { nr, nc });

				// 2. 배열 갱신
				copyMap[nr][nc][0] = -1;
				copyMap[r][c][0] = 0;

				// 물고기 이동시키기
				fishMove(copyMap, pos, score + fish);
			}
		}
	}
}

🐖 Think

- 상어의 이동이 발생할 때 마다 배열과 더불어 해시맵까지 복사해서 사용하였는데, 이를 너무 남발한 기분이 없지않아 있다. 더 깔끔한 방법이 있었을까?