백준 19236번: 청소년 상어

문제 설명

• https://www.acmicpc.net/problem/19236
• (0,0)에 있는 물고기를 잡아먹고 상어가 들어옵니다.
  • 잡아먹은 물고기의 방향이 상어의 방향이 됩니다.
• 물고기들이 이동합니다.
  • 1번부터 이동합니다.
  • 인접한 8칸 중 하나로만 이동할 수 있습니다.
    • 현재 자신의 방향을 가장 먼저, 해당 방향으로 위치변경이 불가능할 경우 반시계방향으로 나머지 칸을 검사합니다.
  • 이동은 빈칸으로의 이동 혹은 물고기와의 위치변경을 의미합니다.
• 물고기의 이동이 끝난 뒤 상어가 이동합니다.
  • 상어는 자신의 방향에서 먹을 수 있는 물고기 중 하나를 먹고 먹은 물고기의 방향을 가집니다.
  • 더 이상 먹을 수 있는 물고기가 없을 때까지 반복합니다.

접근법

• 물고기를 순서대로 이동시켜야 합니다.

  • 2차원 배열에서는 물고기를 순서대로 움직이기 어렵기 때문에 ArrayList에 물고기 정보를 담고 정렬했습니다.
  • 물고기를 번호순으로 정렬시키기 위해 comparable을 사용했습니다.
  • 이때 board의 값이 변경되면 ArrayList의 값도 변경되어야 하기 때문에 board의 값을 갱신할 때마다 list에 새롭게 물고기 정보를 넣었습니다.

• 하나의 위치에서 상어가 먹을 수 있는 물고기는 여럿이며 무엇을 먹어야 가장 좋은 결과를 가져올 지 알 수 없습니다.

  • 백트래킹을 통해 모두 먹어봐야 합니다.
  • 백트래킹은 어떤 값을 취한 뒤 재귀함수를 실행하고, 재귀함수가 끝난 뒤에는 취했던 값을 원래로 되돌려야 합니다.
    • 물고기를 먹기 전 배열을 CopyBoard에 복사했다가 재귀함수 후 Board를 CopyBoard로 덮어씌었습니다.

pseudocode

main(){
	BackT() // (0,0)에 상어를 넣고 백트래킹을 실시합니다.
}

BackT(){
	Init() // board의 값을 기준으로 물고기를 번호순으로 정렬합니다.
    OneCycle() // 물고기들이 움직입니다.
    for(상어의 현재 위치에서 먹을 수 있는 물고기들을 전부 순회합니다){ // (먹이1-1,먹이1-2,먹이1-3)이 있다고 가정하겠습니다.
    	// 여기서는 (food_x,food_y)에 있는 물고기를 먹을 겁니다. // 먹이1-1이라고 가정하겠습니다.
        CopyBoard // 물고기를 먹기 전 어항 속 상황을 저장해 둡니다.
        // Swap전 상어의 위치: (shark.x,shark.y) 먹이의 위치: (food_x,food_y);
        // Swap후 상어의 위치: (food_x,food_y) 먹이의 위치: (shark.x,shark.y);
		Swap(상어의 위치, (food_x,food_y)) // 상어와 (food_x,food_y)위치의 물고기 위치를 바꿉니다.
        // 원래 상어가 있던 위치는 아무런 물고기가 존재하지 않습니다.
        board[shark.x][shark.y].num = 98;
        // 상어의 방향은 잡아먹은 물고기의 방향이 됩니다.
        board[food_x][food_y].d = foodD;
        
        BackT(); // 다음 먹이를 찾아갑니다. // 먹이2-x를 찾아나섭니다.
        
		// 먹이1-2를 먹는 경우를 살펴보기 위해 먹이1-1을 먹기 전으로 board를 되돌립니다.
        board = CopyBoard
    }

}

정답

import java.util.*;

class Main {
	static int MaxVal = 0;
	static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dy = { 0, -1, -1, -1, 0, 1, 1, 1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Fish> lst = new LinkedList<Fish>();
		Fish[][] board = new Fish[4][4];
		int Score = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int num = sc.nextInt();
				int d = sc.nextInt();
				if (i == 0 && j == 0) {
					Score += num;
					Fish f = new Fish(i, j, 99, d - 1);
					board[i][j] = f;
				} else {
					Fish f = new Fish(i, j, num, d - 1);
					board[i][j] = f;
				}
			}
		}

		BackT(0, board[0][0], board, Score, lst);

		System.out.println(MaxVal);

	}

	public static void BackT(int depth, Fish shark, Fish[][] board, int Score, List<Fish> lst) {

		Init(lst, board);
		shark = lst.get(15);
		OneCycle(lst, board);

		List<int[]> fd = Food(shark, board);
		if (fd.size() == 0) {
			MaxVal = Math.max(MaxVal, Score);
			return;
		}

		for (int i = 0; i < fd.size(); i++) {
        	// food_x와 food_y는 잡아먹힐 물고기의 좌표입니다.
			int food_x = fd.get(i)[0];
			int food_y = fd.get(i)[1];
			if (board[food_x][food_y].num == 98)
				continue;

			int foodD = board[food_x][food_y].d;
			int foodNum = board[food_x][food_y].num;
			int[] temp = { shark.x, shark.y };

			// 깊은 복사
			Fish[][] CopyBoard = new Fish[4][4];
			for (int j = 0; j < 4; j++) {
				for (int j2 = 0; j2 < 4; j2++) {
					CopyBoard[j][j2] = new Fish(board[j][j2].x, board[j][j2].y, board[j][j2].num, board[j][j2].d);
				}
			}

			// 상어가 temp위치에 있는 물고기를 먹습니다.
			Swap(temp, fd.get(i), board);

			// shark.x와 shark.y는 '물고기를 잡아먹고 이동한 뒤 상어의 위치'가 아니라 '입력당시 상어의 위치' 입니다.
			board[shark.x][shark.y].num = 98; // temp를 잡아먹기 전 상어가 있던 위치는 빈 칸(98)이 됩니다.
			board[shark.x][shark.y].d = shark.d;
			board[food_x][food_y].d = foodD; // 물고기를 잡아먹었기 때문에 food_x,food_y에는 상어가 있습니다. 상어의 방향을 원래 있던 물고기 방향으로 갱신합니다.

			// 점수 갱신
			Score += foodNum;

			// 다음 먹이 찾기
			BackT(depth + 1, board[food_x][food_y], board, Score, lst);

			// 이동 전으로 롤백
			for (int j = 0; j < 4; j++) {
				for (int j2 = 0; j2 < 4; j2++) {
					board[j][j2] = new Fish(CopyBoard[j][j2].x, CopyBoard[j][j2].y, CopyBoard[j][j2].num,
							CopyBoard[j][j2].d);
				}
			}

			Score -= foodNum;

		}

	}
    // 상어의 현재 위치 및 방향에서 먹을 수 있는 물고기들을 구합니다.
	public static List<int[]> Food(Fish shark, Fish[][] board) {
		List<int[]> fd = new ArrayList<int[]>();
		int x = shark.x;
		int y = shark.y;

		while (true) {
			int nx = x + dx[shark.d];
			int ny = y + dy[shark.d];
			if (0 > nx || nx >= 4 || 0 > ny || ny >= 4) {
				break;
			}
			x = nx;
			y = ny;
			if (board[x][y].num == 98)
				continue;
			int[] temp = { x, y };
			fd.add(temp);
		}
		return fd;
	}

	// 상어를 제외한 모든 물고기를 움직입니다.
	public static void OneCycle(List<Fish> lst, Fish[][] board) { 
		for (int i = 0; i < 15; i++) {
			Fish f = lst.get(i);
			Move(f, board);
			Init(lst, board);
		}
	}

	// 물고기 하나를 움직입니다.
	public static void Move(Fish f, Fish[][] board) {
		if (f.num == 98) return; // 빈칸은 물고기가 아닙니다.
		for (int dd = 0; dd < 8; dd++) {
			int nd = (f.d + dd) % 8;
			int nx = f.x + dx[nd];
			int ny = f.y + dy[nd];
			if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && board[nx][ny].num != 99) {
				f.d = nd;
				int[] b1 = { f.x, f.y };
				int[] b2 = { nx, ny };
				Swap(b1, b2, board);
				return;
			}
		}

	}

	//b1위치에 있는 물고기와 b2위치에 있는 물고기의 위치를 서로 바꿉니다.
	public static void Swap(int[] b1, int[] b2, Fish[][] board) {
		Fish f1 = board[b1[0]][b1[1]];
		Fish f2 = board[b2[0]][b2[1]];

		board[f2.x][f2.y] = new Fish(f2.x, f2.y, f1.num, f1.d);
		board[f1.x][f1.y] = new Fish(f1.x, f1.y, f2.num, f2.d);

	}

	// board를 기준으로 lst의 값을 다시 갱신합니다.
	public static void Init(List<Fish> lst, Fish[][] board) {
		lst.clear();
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				lst.add(board[i][j]);
			}
		}
		Collections.sort(lst);
	}

	static class Fish implements Comparable<Fish> {
		int x;
		int y;
		int num;
		int d;

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

		@Override
		public String toString() {
			return "Fish [x=" + x + ", y=" + y + ", num=" + num + ", d=" + d + "]";
		}

		@Override
		public int compareTo(Fish o) {
			return this.num - o.num;
		}

	}
}

기타

• 푸는 데 정말x100 오래걸렸습니다.
• 백트래킹에서 board를 원래대로 되돌는 걸 구현하는 데 어려움을 겪었습니다.
  • 좌표가 꼬이거나 얕은 복사가 일어나는 문제가 가장 빈번했습니다.
    • 결국 배열을 통으로 copy해서 풀었습니다.
• lst와 board를 동기화해주지 않아 많이 틀렸습니다.
  • (1,1)의 1번물고기와 (2,2)의 2번물고기 위치를 바꿨으면 2번 물고기는 (1,1)에 있어야 하는데 lst를 갱신하지 않으면 여전히 (1,1)의 1번물고기를 사용하게 됩니다.
• 빈칸은 물고기로 취급하면 안됩니다.
  • lst에서 빈칸을 꺼낸 뒤 swap을 실행해 틀렸습니다.