https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
풀이 방법
백트래킹 알고리즘 자체는 쉽게 생각할 수 있었으나 구현이 까다로운 문제였다.
DFS + 백트래킹으로 상어가 이동할 수 있는 모든 경우에 대해 탐색하면서 먹은 물고기 번호의 최댓값을 구한다.
dfs 함수를 호출한 후 먼저 물고기를 모두 이동시키고 상어가 이동가능한 칸을 전부 확인하면서 각 경우에 dfs 함수를 재귀 호출하여 탐색한다. dfs 함수가 끝나면 다음 이동가능한 칸에 대해 새롭게 탐색하기 위해 이전에 탐색하면서 바뀐 상태를 다시 원래의 상태로 복구시켜야 하므로 상어를 이동시키기 전 상태를 복사해놓고 복사본을 이용해 복구시킨다.
주의할 점
문제에서 상어가 이동 시 '물고기가 없는 칸으로는 이동할 수 없다' 라는 말에 대한 해석이 헷갈릴 수 있다. 처음엔 이동할 칸에 물고기가 없으면 아예 지나갈 수도 없다고 생각하여 바로 탐색을 종료하는 것으로 풀어서 틀렸다. 이게 아니라 물고기가 없어도 칸을 지나갈 수 있으며 도착지, 즉 DFS 재귀 호출을 하는 시점이 되는 칸이 물고기가 있는 칸이어야 한다는 뜻이다. 따라서 현재 칸에 물고기가 없어도 그 다음 칸들 중 물고기가 있는 칸이 있을 수 있으므로 이어서 다음 칸에 대해 탐색을 진행해야 한다.
삽질했던 부분!
현재 상태를 복사하여 복사본을 만들 땐 깊은 복사를 잘 했으나 백트래킹 시 원래의 상태로 복구시킬 때 얕은 복사를 하고 있었다.. 얕은 복사는 주소가 복사되므로 다음 이동 가능한 칸 탐색할 때 원래의 상태가 바뀌면 복사본의 상태까지 바뀌어 복사본의 상태를 계속 유지할 수 없게 된다! (이게 예제로는 안잡히는 문제라 삽질을 꽤 했다....) 얕은 복사, 깊은 복사 주의하자!
코드
import java.io.*;
public class Main {
public static class Fish {
int x;
int y;
int d; // 방향
boolean alive; // 생존 여부
public Fish(int x, int y, int d, boolean alive) {
this.x = x;
this.y = y;
this.d = d;
this.alive = alive;
}
}
static int[][] board = new int[4][4];
static Fish[] fishes = new Fish[17];
static int answer = 0;
static int[] dx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
static int[] dy = {0, 0, -1, -1, -1, 0, 1, 1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0; i<4; i++) {
String[] line = br.readLine().split(" ");
for(int j=0; j<8; j += 2) {
int num = Integer.parseInt(line[j]); // 번호
int direct = Integer.parseInt(line[j+1]); // 방향
board[i][j / 2] = num;
fishes[num] = new Fish(i, j/2, direct, true);
}
}
// (0, 0) 에 있는 물고기 먹음
int fNum = board[0][0];
Fish fish = fishes[fNum];
fish.alive = false;
board[0][0] = -1;
move(0, 0, fNum, fish.d);
System.out.println(answer);
}
public static void move(int sx, int sy, int total, int d) {
// 물고기 이동
moveFish(sx, sy);
// 상태 복구를 위한 복사
int[][] temp = new int[4][4];
Fish[] tempFishes = new Fish[17];
copy(temp, tempFishes, board, fishes);
int step = 1;
while(true) {
int nx = sx + dx[d] * step;
int ny = sy + dy[d] * step;
if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) { // 경계를 넘으면 이동 불가
answer = Math.max(answer, total);
break;
}
// 물고기가 없는 칸이면 건너뜀
if(board[nx][ny] == -1) {
step++;
continue;
}
// 해당 칸으로 이동하여 물고기를 먹음
int fNum = board[nx][ny];
Fish target = fishes[fNum];
target.alive = false;
board[nx][ny] = -1;
move(nx, ny, total + fNum, target.d);
// 백트래킹
copy(board, fishes, temp, tempFishes);
step++; // 한 칸 더 이동
}
}
public static void moveFish(int sx, int sy) {
for(int i=1; i<=16; i++) {
Fish fish = fishes[i];
if(!fish.alive) { // 죽은 물고기인 경우
continue;
}
boolean moved = false; // 이동 여부
int curd = fish.d; // 현재 방향
while(!moved) {
int nx = fish.x + dx[curd];
int ny = fish.y + dy[curd];
// 경계를 벗어나거나 상어가 있으면 반시계 회전
if((nx < 0 || nx >= 4 || ny < 0 || ny >= 4) || (sx == nx && sy == ny)) {
curd = (curd + 1 > 8) ? 1 : curd + 1; // 회전한 후의 방향
if(curd == fish.d) { // 처음 방향으로 돌아온 경우엔 탈출
break;
}
continue;
}
// 물고기 이동 -> 서로의 위치를 바꿈
switchFish(nx, ny, fish.x, fish.y, board[nx][ny], i, curd);
moved = true;
}
}
}
public static void switchFish(int nx, int ny, int x, int y, int num1, int num2, int direct) {
// 이동할 곳에도 물고기가 있으면 옮겨줌
if(num1 != -1) {
fishes[num1].x = x;
fishes[num1].y = y;
}
fishes[num2].x = nx;
fishes[num2].y = ny;
fishes[num2].d = direct;
board[nx][ny] = num2;
board[x][y] = num1;
}
public static void copy(int[][] board, Fish[] fishes, int[][] _board, Fish[] _fishes) {
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
board[i][j] = _board[i][j];
}
}
for(int i=1; i<=16; i++) {
Fish fish = _fishes[i];
fishes[i] = new Fish(fish.x, fish.y, fish.d, fish.alive);
}
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 9017 크로스 컨트리 자바(java) (0) | 2023.12.21 |
|---|---|
| 백준 14501 퇴사 자바(java) (1) | 2023.12.21 |
| 백준 14889 스타트와 링크 자바(java) (1) | 2023.12.19 |
| 백준 16235 나무 재테크 자바(java) (0) | 2023.12.19 |
| 백준 1182 부분수열의 합 자바(java) (0) | 2023.12.05 |