문제 설명
- 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을 실행해 틀렸습니다.
기록하고 정리하는 걸 좋아하는 개발자.