BOJ - 19236 청소년 상어

19236 청소년 상어 : https://www.acmicpc.net/problem/19236

---

Problem

---

Solve

상어가 배열에서 이동할 수 있는 모든 경우의 수를 파악하면서 상어가 잡아 먹은 물고기 번호의 최대 합을 구하는 것을 보고 딱 백트래킹 냄새가 났다.
이번 구현에서는 백트래킹 대신 배열의 깊은 복사하였다.

구현은 DFS에서 물고기를 이동시키고, 상어는 현재 방향에서 이동할수 있는 경우의 수 3가지를 가지고 조건에 맞는 이동이라면 DFS를 호출하는 식으로 구현했다.
그리고 백트래킹을 위해 map과 물고기 정보 배열 Fish를 깊은 복사하는 함수를 구현했다.

구현 순서는 아래와 같다.
1. 상어는 최초에 (0,0)에 있는 물고기를 잡아먹고 시작한다.

• (0,0)에 있는 물고기 정보를 isDie = true로 변경하고 map[0][0]에 상어 표시 -1로 갱신후 해당 물고기의 번호와 상어 좌표, 상어 방향, map, 물고기 정보를 담은 배열을 DFS의 arguments로 보내준다.

2. DFS

• 최대로 먹은 물고기의 합을 갱신
• 물고기가 움직인 결과를 매개변수로 받은 map과 Fishs에 갱신한다.(isDie == true인 물고기는 무시한다.)
• 상어가 이동할때 이동한 좌표에 물고기가 있고 배열 범위 밖으로 벗어나지 않는 다면 해당 좌표 물고기를 isDie=true로 변경하고 상어는 해당 물고기의 방향을 얻고 map과 Fishes를 깊은 복사 후 DFS 재귀

---

Code

public class 청년상어 {
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};

	static int answer;

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

		int[][] map = new int[4][4];
		// List<Fish> fishList = new ArrayList<>();
		Fish[] fishes = new Fish[17];
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 4; j++) {
				int number = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken()) - 1;

				map[i][j] = number;
				fishes[number] = new Fish(number, i, j, d, false, false);
			}
		}

		Fish eatFish = fishes[map[0][0]];
		eatFish.isDie = true;
		map[0][0] = -1;
		Fish[] cloneFishes = fishClone(fishes);
		int[][] cloneMap = mapClone(map);

		answer = 0;

		hunt(0, 0, eatFish.d, eatFish.number, cloneMap, cloneFishes);

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//물고기 이동
	static void moveFish(int[][] map, Fish[] fishes) {
		for (int s=1;s<17;s++) {
			Fish currentFish = fishes[s];
            //잡아먹힌 물고기는 제외한다.
			if(currentFish.isDie) continue;
			int currentY = currentFish.y;
			int currentX = currentFish.x;
            //총 8개의 이동 방향
			for (int i = 0; i < 8; i++) {
				int nd = (currentFish.d + i)%8;
				int ny = currentFish.y + dy[nd];
				int nx = currentFish.x + dx[nd];

				//배열 범위 밖이거나 상어가 있는 좌표에는 이동할수 없다.
				if (ny < 4 && nx < 4 && ny >= 0 && nx >= 0 && map[ny][nx] != -1) {
                	//빈 공간이면 물고기 그냥 이동.
					if (map[ny][nx] == 0) {
						map[currentY][currentX] = 0;
						map[ny][nx] = currentFish.number;
						currentFish.y = ny;
						currentFish.x = nx;
					}
                    //물고기가 이미 있는 곳이라면 현재 물고기와 이미 좌표에 존재하던 물고기의 위치를 변경해준다.
                    else {
						Fish changeFish = fishes[map[ny][nx]];

						changeFish.y = currentY;
						changeFish.x = currentX;
						currentFish.y = ny;
						currentFish.x = nx;

						map[currentY][currentX] = changeFish.number;
						map[ny][nx] = currentFish.number;

					}
					currentFish.d = nd;
					break;
				}
			}
		}
	}

	//DFS
	static void hunt(int sy, int sx, int sd, int eat, int[][] map, Fish[] fishes) {
    	//현재 상어가 먹은 물고기 번호 총합의 최대값을 갱신.
		answer = Math.max(answer, eat);

		//물고기 움직임
		moveFish(map, fishes);

		//상어 움직임
		//해당 방향으로 이동가능한 3가지의 좌표로 dfs한다.
		//다른 재귀에 영향을 주지 않도록 map과 fishList는 clone해서 변경된 정보를 갱신후 dfs한다.
		for (int i = 1; i < 4; i++) {
			int nsy = sy+dy[sd]*i;
			int nsx = sx+dx[sd]*i;
			if(nsy<4 && nsx<4 && nsx>=0 && nsy>=0 && map[nsy][nsx] != 0){
				Fish eatFish = fishes[map[nsy][nsx]];
				int nsd = eatFish.d;

				int[][] cloneMap = mapClone(map);
				Fish[] cloneFishes = fishClone(fishes);
				cloneMap[sy][sx] = 0;
				cloneMap[nsy][nsx] = -1;
				cloneFishes[eatFish.number].isDie = true;

				hunt(nsy, nsx, nsd, eat+eatFish.number, cloneMap, cloneFishes);
			}
		}
	}

	static int[][] mapClone(int[][] map){
		int[][] cloneMap = new int[4][4];

		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				cloneMap[i][j] = map[i][j];
			}
		}

		return cloneMap;
	}

	static Fish[] fishClone(Fish[] fish){
		Fish[] cloneFish = new Fish[17];

		for(int i=1;i<17;i++){
			Fish f = fish[i];
			cloneFish[i] = new Fish(f.number, f.y, f.x, f.d, f.isDie, f.isShark);
		}

		return cloneFish;
	}

	static class Fish {
		int number;
		int y;
		int x;
		int d;
		boolean isDie;
		boolean isShark;

		public Fish(int number, int y, int x, int d, boolean isDie, boolean isShark) {
			this.number = number;
			this.y = y;
			this.x = x;
			this.d = d;
			this.isDie = isDie;
			this.isShark = isShark;
		}
	}
}

---

Result

문제를 풀고나면 풀만한 문제인데, 시간이 너무 오래걸리는것과 처음 생각했던 방향성이 틀려서 멘탈이 흔들리는게 문제인것같다..

---

Reference