https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
코드설명
시뮬레이션 + 구현 + 백트래킹 을 활용하는 문제입니다.
문제에서 가장 중요한점은, 어떻게 물고기들과 상어를 표현할 것인가입니다.
저는 처음에는 물고기의 번호 순서에 따라서 물고기가 순서대로 이동한다는 조건에 PriorityQueue(우선순위큐)를 활용하여서 진행하려했지만, 이렇게 할경우 Queue를 계속해서 채워줘야하고, 가장 큰 문제점은, 특정 물고기의 정보를 가져올때 N번이동해야하며, 서로 Swap할때는 너무나 어려워집니다.
그렇기에 아래와 같이 물고기 배열을 전역적으로 선언하여 관리합니다. 이와 같이하면 fishArr[1], fishArr[2]로 단순하게 물고기 순서대로 관리할 수 있으며, 이후에 Swap할때도 쉽게 접근할 수 있습니다.
public static Fish[] fishArr = new Fish[17];
또한 단순히 물고기들의 번호를 Map에 저장시켜두어서 손쉽게 물고기들의 이동처리를 진행하고 배열의 위치를 사용할 수 있었습니다.
public static int[][] map;
1. 입력 처리:
- 4x4 크기의 격자판에 각 물고기의 번호와 방향이 주어집니다.
- 초기에 상어의 위치와 방향, 그리고 물고기들의 정보를 초기화합니다.
2. 물고기 이동 (fishMove 메서드):
- 각 물고기에 대해 현재 위치에서 이동 가능한 방향으로 이동합니다.
- 이동할 수 없는 경우는 범위를 벗어나거나 상어가 있는 경우입니다.
- 이동 가능한 경우에는 해당 위치의 물고기와 위치를 교환하고, 격자판을 업데이트합니다.
3. 상어 이동 및 물고기 먹기 (simulate 메서드):
- 상어는 현재 방향으로 1부터 3까지의 거리를 이동하며 먹을 수 있는 물고기를 찾습니다.
- 물고기를 먹으면 해당 물고기의 정보를 업데이트하고, 상어의 상태도 업데이트합니다.
- 재귀 호출을 사용하여 가능한 모든 경우를 시뮬레이션합니다.
4. 재귀 호출 및 원상복구:
- 각 단계에서 상어가 물고기를 먹고 나면 해당 상태를 저장하고, 재귀 호출이 끝나면 다시 원래의 상태로 돌아갑니다.
- 이를 통해 다양한 경우의 수를 확인하며 최대값을 찾습니다.
3번과정에서 simulate함수에서 모든 경우를 시뮬레이트하기 위해서 물고기가 이동하기전의 Map[4][4] 배열, FishArr[17] 객체 배열을 미리 저장해놓은뒤, simulate함수가 모든 경우를 조사한뒤에는 다시 원상복구 시키고 해당 스택프레임에서 벗어나도록 처리합니다. 이때, 다시 원상복구 시키는 코드의 위치가 조금 헷갈릴 수 있는데 simulate 함수가 재귀적으로 호출되어 level 이 증가한뒤 종료될때 원상복구 하는 코드를 추가시키도록합니다. 처음에는 move 함수마다 넣어서 처리하였지만 이렇게 하지않아야 이전 simulate함수가 종료되며 원상복구시킵니다. 또한, move for문 밖에 두어야 fishMove한 map을 기준으로 검사하기에 그렇습니다.
제가 실수했던 부분들에 대해 정리해보면,
1. 아래와 같이 Fish 부분을 지역변수 내에서 재귀함수마다 처리해주어야합니다. 처음에 전역변수로 두어 올바르게 값이 저장되지않고, 중간에 변경되었습니다..
Fish[] storeFishArr = new Fish[17];
for(int i=1; i<17;i++) {
storeFishArr[i] = new Fish(fishArr[i].r, fishArr[i].c, fishArr[i].idx, fishArr[i].dir, fishArr[i].eaten);
}
2. 상어가 물고기를 먹고나서 위치도 바꿔줘야합니다. 처음에는 위치를 바꿔주지않았었습니다.
Shark storeOriginFish = new Shark(shark.r, shark.c, shark.dir, shark.eat);
fishArr[map[nr][nc]].eaten = true;
shark.r = nr; shark.c = nc; shark.dir = fishArr[map[nr][nc]].dir; shark.eat += fishArr[map[nr][nc]].idx;
simulate(level + 1);
fishArr[map[nr][nc]].eaten = false;
shark = storeOriginFish;
3. 물고기가 이동할 수 없는 경우는 오직, 상어가 있거나 공간의 경계를 넘는칸입니다. 처음에 이동할 칸의 물고기가 죽어있다면 이동하지 않도록 처리했습니다. 물고기가 죽어있다는 의미는 공간이 비어있다는 의미입니다.
//만약 해당 물고기가 이미 죽어있다면,
// if( fishArr[map[nr][nc]].eaten == true) {
// dirTemp = (dirTemp + 1) % 8;
// continue;
// }
4. map[nr][nc] = i 의 순서를 마지막으로합니다. 혹은 다른 변수에 저장시켜두고 사용하면 되겠습니다.
fishArr[i].r = nr;
fishArr[i].c = nc;
fishArr[i].dir = dirTemp;
map[r][c] = map[nr][nc];
fishArr[map[nr][nc]].r = r;
fishArr[map[nr][nc]].c = c;
map[nr][nc] = i; //이때 순서를 유의해야합니다. map[nr][nc]가 fishArr 앞에 존재한다면 변환 중에 영향이 발생합니다.
break; //한번이라도 이동한다면 이동완료로 처리합니다.
처음에 이렇게 Memory[4][4]의 정보와 Fish[17]의 정보를 계속해서 저장하면서 Stack Frame을 들어갈경우 메모리초과가 나올까봐 걱정했지만, 메모리 제한은 512MB이고, Memor[4][4]의 Memory 크기는 4 x 4 x 4 = 64 byte 입니다.
Fish[17]은 4 * 5 * 17 = 340 byte 입니다. 만약 상어가 모든경우를 탐색할경우의 수는, 3개의 칸을 선택하는 횟수가 최악의 경우 16번 이므로 3^16 입니다.(사실 더 줄어들지만 최악의 경우로 생각합니다.) 계산하면, 3^16 *340 = 17,347,828,563 byte가 나옵니다. 이걸 MB로 변환할경우 16.481 MB 입니다. 메모리초과를 걱정할 필요는 없을 것 같습니다.
실제로 백준결과 확인결과 14416 kb 가 나왔습니다. -> 14416 kb = 14.05 MB 입니다. MB = KB / 1024 입니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K, T;
public static int answer = 0;
public static int[] arr;
public static int[][] map;
public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //12시방향부터 반시계방향으로 회전합니다.
public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
public static Shark shark = new Shark(0, 0, 0, 0);
public static Fish[] fishArr = new Fish[17];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
map = new int[4][4];
for(int i=0;i<4;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
int a = Integer.parseInt(st.nextToken()); //물고기 번호.
int b = Integer.parseInt(st.nextToken()); //방향을 의미.
if( i == 0 && j == 0) {
Fish fish = new Fish(i, j, a, b - 1, true);
shark = new Shark(i, j, b-1, a);
map[i][j] = a;
fishArr[a] = fish;
}
else {
Fish fish = new Fish(i, j, a, b - 1, false);
map[i][j] = a;
fishArr[a] = fish;
}
}
}
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
answer = Math.max(answer, shark.eat);
//fishMove 이전에 처리해야 올바르게 저장되어 함수가 끝난 후 fishmove 이전의 상태로 돌아옵니다.
int[][] storeMap = new int[4][4];
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
storeMap[k][h] = map[k][h];
}
}
//1. 먼저 물고기를 이동처리하겠습니다.이떄 물고기의 값도 저장시켜두어야합니다.
Fish[] storeFishArr = new Fish[17];
for(int i=1; i<17;i++) {
storeFishArr[i] = new Fish(fishArr[i].r, fishArr[i].c, fishArr[i].idx, fishArr[i].dir, fishArr[i].eaten);
}
//이동하기 전 물고기의 위치를 미리 저장해둡시다.
//여기서 진짜 map의 정보를 담아두고 완전탐색을 진행하면 걱정되는게 memory 초과이다.
fishMove();
//상어를 움직일 것 입니다. 최대맵의 크기는 4 이므로 최대값은 4입니다.
for(int move = 1; move < 4; move++) {
//2. 상어가 각 물고기를 먹을 것입니다.
int nr = shark.r + dx[shark.dir] * move;
int nc = shark.c + dy[shark.dir] * move;
if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) break;
if( fishArr[map[nr][nc]].eaten == true ) continue; //만약 이미 먹은 물고기라면 PASS 합니다.
Shark storeOriginFish = new Shark(shark.r, shark.c, shark.dir, shark.eat);
fishArr[map[nr][nc]].eaten = true;
shark.r = nr; shark.c = nc; shark.dir = fishArr[map[nr][nc]].dir; shark.eat += fishArr[map[nr][nc]].idx;
simulate(level + 1);
fishArr[map[nr][nc]].eaten = false;
shark = storeOriginFish;
}
//원상복구. 모든 상어가 움직일 수 없다면 해당 스택이 끝나면서 원상복구되어 부모의 Stack Frame으로 돌아갑니다.
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
map[k][h] = storeMap[k][h];
}
}
for(int i=1; i<17;i++) {
fishArr[i] = storeFishArr[i];
}
}
public static void fishMove() {
for(int i = 1; i< 17; i++) {
if(fishArr[i].eaten == true) continue; //만약 이미 먹힌 물고기라면 작업하지 않습니다.
Fish temp = fishArr[i];
int r = temp.r;
int c = temp.c;
int dirTemp = temp.dir;
for(int dir = 0; dir<8;dir++) {
int nr = temp.r + dx[dirTemp];
int nc = temp.c + dy[dirTemp];
//만약 범위를 벗어날경우 무시합니다.
if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) {
dirTemp = (dirTemp + 1) % 8;
continue;
}
//이동할 수 없는경우는 상어가 있는경우이다.
if(nr == shark.r && nc == shark.c) {
dirTemp = (dirTemp + 1) % 8;
continue;
}
//이동할 수 있는 칸은 빈칸과 다른 물고기가 있는 칸 입니다.
//만약 갈 수 있는경우라면 해당 위치의 물고기와 Swap합니다.
fishArr[i].r = nr;
fishArr[i].c = nc;
fishArr[i].dir = dirTemp;
map[r][c] = map[nr][nc];
fishArr[map[nr][nc]].r = r;
fishArr[map[nr][nc]].c = c;
map[nr][nc] = i; //이때 순서를 유의해야합니다. map[nr][nc]가 fishArr 앞에 존재한다면 변환 중에 영향이 발생합니다.
break; //한번이라도 이동한다면 이동완료로 처리합니다.
}
}
}
}
class Fish {
int r;
int c;
int idx;
int dir;
boolean eaten;
public Fish(int r, int c, int idx, int dir, boolean eaten) {
this.r = r;
this.c = c;
this.idx = idx;
this.dir = dir;
this.eaten = eaten;
}
}
class Shark{
int r;
int c;
int dir;
int eat;
public Shark(int r, int c, int dir, int eat) {
this.r = r;
this.c = c;
this.dir = dir;
this.eat = eat;
}
}
처음에 실패한 코드입니다. storeFishArr의 참조문제, fishMove에서 빈칸일경우에 이동할 수 있도록 처리못한 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K, T;
public static int answer = 0;
public static int[] arr;
public static int[][] map;
public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //12시방향부터 반시계방향으로 회전합니다.
public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
public static Shark shark = new Shark(0, 0, 0, 0);
public static Fish[] fishArr = new Fish[17];
public static Fish[] storeFishArr = new Fish[17];
public static int sharkEat = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer st = new StringTokenizer(br.readLine());
map = new int[4][4];
for(int i=0;i<4;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
int a = Integer.parseInt(st.nextToken()); //물고기 번호.
int b = Integer.parseInt(st.nextToken()); //방향을 의미.
if( i == 0 && j == 0) {
Fish fish = new Fish(i, j, a, b - 1, true);
shark.eat += fish.idx;
shark.dir = fish.dir;
map[i][j] = a;
fishArr[a] = fish;
storeFishArr[a] = new Fish(i, j, a, b-1, true);
}
else {
Fish fish = new Fish(i, j, a, b - 1, false);
map[i][j] = a;
storeFishArr[a] = fish;
fishArr[a] = fish;
storeFishArr[a] = new Fish(i, j, a, b-1, false);
}
}
}
simulate(0);
System.out.println("END");
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
System.out.print(" "+map[k][h]);
}
System.out.println();
}
System.out.println();
System.out.println(answer);
}
public static void simulate(int level) {
System.out.println("level:"+level+"startEat:"+shark.eat);
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
System.out.print(" "+map[k][h]+" ("+ fishArr[map[k][h]].dir +" "+fishArr[map[k][h]].eaten+")");
}
System.out.println();
}
System.out.println();
answer = Math.max(answer, shark.eat);
int[][] storeMap = new int[4][4];
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
storeMap[k][h] = map[k][h];
}
}
//1. 먼저 물고기를 이동처리하겠습니다.이떄 물고기의 값도 저장시켜두어야합니다.
for(int i=1; i<17;i++) {
storeFishArr[i].r = fishArr[i].r;
storeFishArr[i].c = fishArr[i].c;
storeFishArr[i].dir = fishArr[i].dir;
storeFishArr[i].idx = fishArr[i].idx;
storeFishArr[i].eaten = fishArr[i].eaten;
}
//이동하기 전 물고기의 위치를 미리 저장해둡시다.
fishMove();
//상어를 움직일 것 입니다. 최대맵의 크기는 4 이므로 최대값은 4입니다.
for(int move = 1; move < 4; move++) {
//2. 상어가 각 물고기를 먹을 것입니다.
int nr = shark.r + dx[shark.dir] * move;
int nc = shark.c + dy[shark.dir] * move;
if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) break;
if( fishArr[map[nr][nc]].eaten == true ) continue; //만약 이미 먹은 물고기라면 PASS 합니다.
System.out.print("Shark Pos !!! "+ shark.r+" "+shark.c+"Shark Dir"+shark.dir+" Shark Eat"+ nr+" "+nc);
int beforeSharkDir = shark.dir;
int beforeSharkEat = shark.eat;
fishArr[map[nr][nc]].eaten = true;
shark.dir = fishArr[map[nr][nc]].dir;
shark.eat += fishArr[map[nr][nc]].idx;
simulate(level + 1);
fishArr[map[nr][nc]].eaten = false;
shark.dir = beforeSharkDir;
shark.eat = beforeSharkEat;
}
//원상복구.
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
map[k][h] = storeMap[k][h];
}
}
//1. 먼저 물고기를 이동처리하겠습니다.이떄 물고기의 값도 저장시켜두어야합니다.
for(int i=1; i<17;i++) {
fishArr[i].r = storeFishArr[i].r;
fishArr[i].c = storeFishArr[i].c;
fishArr[i].dir = storeFishArr[i].dir;
fishArr[i].idx = storeFishArr[i].idx;
fishArr[i].eaten = storeFishArr[i].eaten;
}
}
public static void fishMove() {
for(int i = 1; i< 17; i++) {
if(fishArr[i].eaten == true) continue; //만약 이미 먹힌 물고기라면 작업하지 않습니다.
Fish temp = fishArr[i];
int r = temp.r;
int c = temp.c;
int dirTemp = temp.dir;
System.out.println("Original"+dirTemp);
for(int dir = 0; dir<8;dir++) {
int nr = temp.r + dx[dirTemp];
int nc = temp.c + dy[dirTemp];
System.out.println("dirTemp Working well?"+dirTemp);
//만약 범위를 벗어날경우 무시합니다.
if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) {
dirTemp = (dirTemp + 1) % 8;
continue;
}
//이동할 수 없는경우는 상어가 있는경우이다.
if(nr == shark.r && nc == shark.c) {
dirTemp = (dirTemp + 1) % 8;
continue;
}
if( fishArr[map[nr][nc]].eaten == true) {
dirTemp = (dirTemp + 1) % 8;
continue;
}
//이동할 수 있는 칸은 빈칸과 다른 물고기가 있는 칸 입니다.
//만약 갈 수 있는경우라면 해당 위치의 물고기와 Swap합니다.
fishArr[i].r = nr;
fishArr[i].c = nc;
fishArr[i].dir = dirTemp;
map[r][c] = map[nr][nc];
fishArr[map[nr][nc]].r = r;
fishArr[map[nr][nc]].c = c;
map[nr][nc] = i; //이때 순서를 유의해야합니다. map[nr][nc]가 fishArr 앞에 존재한다면 변환 중에 영향이 발생합니다.
break; //한번이라도 이동한다면 이동완료로 처리합니다.
}
}
}
}
class Fish implements Comparable<Fish>{
int r;
int c;
int idx;
int dir;
boolean eaten;
public Fish(int r, int c, int idx, int dir, boolean eaten) {
this.r = r;
this.c = c;
this.idx = idx;
this.dir = dir;
this.eaten = eaten;
}
@Override
public int compareTo(Fish other) {
if(this.idx > other.idx) { //오름차순으로 정렬합니다.
return 1;
}else {
return -1;
}
}
}
class Shark{
int r;
int c;
int dir;
int eat;
public Shark(int r, int c, int dir, int eat) {
this.r = r;
this.c = c;
this.dir = dir;
this.eat = eat;
}
}