[BOJ19236] 청소년 상어 (Java, 백트래킹, 시뮬레이션)

문제 링크 

https://www.acmicpc.net/problem/19236

 

풀이

백트래킹이 약한 나에게 있어 정말 실수 연발했던 문제였다 (그래도 백트래킹 재미있다)

 

① 입력 데이터 초기화 후 상어가 `(0, 0)` 에 물고기를 먹고 그 방향을 가진다

 

② 모든 물고기들이 이사를 시작한다
- 작은 번호부터 순차적으로 이사
- 이동 가능한 위치를 찾을 때 까지 반 시계 방향으로 제자리 회전하면서 빈칸 또는 물고기를 찾아 위치를 교환한다
- 상어가 있거나, 맵의 경계를 벗어난 경우 다음 위치로 회전
- 만약 이사 가능한 위치가 없다면 제자리를 유지한다

③ 상어가 먹이를 탐색한다
- 상어는 빈칸으로 이동 불가하고 이동하는 도중에 있는 물고기는 먹지 않는다
- 이때, 큰 물고기를 먹는다고 항상 최적의 해를 보장하지 않는다 (*백트래킹 요구)
- 먹이가 존재하지 않거나, 맵을 벗어난 경우 집으로 돌아간다 (*재귀 종료조건)

 

④ 먹이가 존재하는 경우 각각 재귀 호출하여 최대값을 구한다

 

물고기가 이사할 위치를 찾을 때 방향 정보는 나머지(mod) 연산으로 쉽게 찾을 수 있다

문제 설명 그대로 방향 정보를 정의하고 int dir = (물고기 방향 + i ) % 8 계산하여 구할 수 있다
private static final int[][] DIR = {
   // 위     왼쪽 위                                                          오른쪽 위
  {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}
};

 

실수1. 

- 상어가 바라보는 방향에서 최대값의 생선을 먹는다고 해서 최적의 해를 찾을 수 없다
- 모든 경우을 고려해야 하기 때문에 백트래킹 풀이 요구했다

 

실수2.

물고기가 이사 가능한 위치를 찾을 때 제자리에서 회적하는 형태인데, `x, y, dir` 변수를 누적하도록 처리하여 문제가 풀리지 않았다

private static void moveFishes(int[][][] arr, int sharkX, int sharkY) {  
    for(int no = 1; no <= 16; no++) {  
        int[] position = findFish(arr, no);  

        if(position == null) continue;  

        int x = position[0];  
        int y = position[1];  
        int d = arr[x][y][1]; // 현재 물고기의 방향

        // 빈칸이거나 다른 물고기가 있는 칸으로 이동 (없는 경우 제자리 유지)  
        for(int i = 0; i < 8; i++) {  
            int dir = (d + i) % 8;  // 다음 방향
            int dx = x + DIR[dir][0]; // 이전 잘못 풀이 => x += DIR[dir][0]; 
            int dy = y + DIR[dir][1]; // 이전 잘못 풀이 => y += DIR[dir][1];

            if(dx < 0 || dy < 0 || dx >= N || dy >= N) continue;  
            if(dx == sharkX && dy == sharkY) continue;  

            arr[x][y][0] = arr[dx][dy][0];  
            arr[x][y][1] = arr[dx][dy][1];  

            arr[dx][dy][0] = no;  
            arr[dx][dy][1] = dir; // 현재 회전 방향 가짐  
            break;  
        }  

    }  
}

 

실수3. 오타

 백트래킹 호출시 매번 3차원 배열(맵 정보)를 깊은 복사하여 사용해야 하는데 초반 설계시 maps를 지정해두고 수정하지 않아 데이터가 꼬이고 난리도 아니었다. 아래 재귀 메서드에서 maps가 사용되는 건 첫줄이 끝인데, 이후에 maps를 arr로 수정하지 않은게 눈에 보이지 않아 피가 말렸다 ... ㅋㅋ 

private static void rec(int[][][] maps, int sharkX, int sharkY, int ate) { 
    int[][][] arr = copy(maps); // *중요 

    // 상어가 잡아 먹는다  
    int total = ate + arr[sharkX][sharkY][0]; // 실수* maps 사용 
    arr[sharkX][sharkY][0] = -1;  

    // 물고기가 이동한다  
    moveFishes(arr, sharkX, sharkY);  

    // 상어가 다음으로 이동할 위치의 먹이를 찾는다  
    List<int[]> target = findNextTarget(arr, sharkX, sharkY);  
    if(target.isEmpty()) {  
        result = Math.max(result, total);  
        return;  
    }  

    // 이동하기 전 현재 위치의 정보를 초기화 (maps 사용하는 실수*)  
    arr[sharkX][sharkY][0] = -1;  
    arr[sharkX][sharkY][1] = -1;  
    for(int[] next : target) {  
        rec(arr, next[0], next[1], total);  
    }  
}

 

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {

	private static StringBuilder sb = new StringBuilder();  
	private static InputProcessor inputProcessor = new InputProcessor();  
	  
	public static void main(String[] args) {  
	    input();  
	    pro();  
	    output();  
	}  
	  
	private static final int N = 4;  
	private static final int[][] DIR = {  
	        {-1, 0},  
	        {-1, -1},  
	        {0, -1},  
	        {1, -1},  
	        {1, 0},  
	        {1, 1},  
	        {0, 1},  
	        {-1, 1}  
	};  
	  
	private static int result;  
	private static int[][][] initMap;  
	  
	private static void input() {  
	    initMap = new int[N][N][2]; // 0: 번호, 1: 방향  
	  
	    for(int i = 0; i < N; i++) {  
	        for(int j = 0; j < N; j++) {  
	            int no = inputProcessor.nextInt();  
	            int dir = inputProcessor.nextInt();  
	  
	            initMap[i][j][0] = no;  
	            initMap[i][j][1] = dir - 1;  
	        }  
	    }  
	  
	    result = Integer.MIN_VALUE;  
	}  
	  
	private static void pro() {  
	    rec(initMap, 0, 0, 0);  
	  
	    sb.append(result);  
	}  
	  
	private static void rec(int[][][] maps, int sharkX, int sharkY, int ate) {  
	    int[][][] arr = copy(maps);  
	  
	    // 상어가 잡아 먹는다  
	    int total = ate + arr[sharkX][sharkY][0]; // 실수* maps에 갱신  
	    arr[sharkX][sharkY][0] = -1;  
	  
	    // 물고기가 이동한다  
	    moveFishes(arr, sharkX, sharkY);  
	  
	    // 상어가 다음으로 이동할 위치의 먹이를 찾는다  
	    List<int[]> target = findNextTarget(arr, sharkX, sharkY);  
	    if(target.isEmpty()) {  
	        result = Math.max(result, total);  
	        return;  
	    }  
	  
	    // 이동하기 전 현재 위치의 정보를 초기화 (maps 사용하는 실수*)  
	    arr[sharkX][sharkY][0] = -1;  
	    arr[sharkX][sharkY][1] = -1;  
	    for(int[] next : target) {  
	        rec(arr, next[0], next[1], total);  
	    }  
	}  
	  
	private static int[][][] copy(int[][][] base) {  
	    int[][][] temp = new int[N][N][2];  
	    for(int i = 0; i < N; i++) {  
	        for(int j = 0; j < N; j++) {  
	            temp[i][j][0] = base[i][j][0];  
	            temp[i][j][1] = base[i][j][1];  
	        }  
	    }  
	  
	    return temp;  
	}  
	  
	// 물고기 번호가 낮은 순서로 찾는다  
	private static void moveFishes(int[][][] arr, int sharkX, int sharkY) {  
	    for(int no = 1; no <= 16; no++) {  
	        int[] position = findFish(arr, no);  
	  
	        if(position == null) continue;  
	  
	        int x = position[0];  
	        int y = position[1];  
	        int d = arr[x][y][1]; // 현재 물고기의 방향
	  
	        // 빈칸이거나 다른 물고기가 있는 칸으로 이동 (없는 경우 제자리)  
	        for(int i = 0; i < 8; i++) {  
	            int dir = (d + i) % 8;  
	            int dx = x + DIR[dir][0];  
	            int dy = y + DIR[dir][1];  
	  
	            if(dx < 0 || dy < 0 || dx >= N || dy >= N) continue;  
	            if(dx == sharkX && dy == sharkY) continue;  
	  
	            arr[x][y][0] = arr[dx][dy][0];  
	            arr[x][y][1] = arr[dx][dy][1];  
	  
	            arr[dx][dy][0] = no;  
	            arr[dx][dy][1] = dir; // 현재 회전 방향 가짐  
	            break;  
	        }  
	  
	    }  
	}  
	  
	private static int[] findFish(int[][][] arr, int no) {  
	    for(int i = 0; i < N; i++) {  
	        for(int j = 0; j < N; j++) {  
	            if(arr[i][j][0] == no) {  
	                return new int[] {i, j};  
	            }  
	        }  
	    }  
	  
	    return null;  
	}  
	  
	private static List<int[]> findNextTarget(int[][][] arr, int sharkX, int sharkY) {  
	    List<int[]> targets = new ArrayList<>();  
	    int x = sharkX;  
	    int y = sharkY;  
	    int d = arr[sharkX][sharkY][1]; // 방향 정보  
	    for(int i = 0; i < N; i++) {  
	        x += DIR[d][0];  
	        y += DIR[d][1];  
	  
	        if(x < 0 || y < 0 || x >= N || y >= N) break;  
	  
	        if(arr[x][y][0] != -1) {  
	            targets.add(new int[] {x, y});  
	        }  
	    }  
	  
	    return targets;  
	}  
	  
	private static void output() {  
	    try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {  
	        bw.write(sb.toString());  
	        bw.flush();  
	    } catch (IOException e) {  
	        throw new RuntimeException(e);  
	    }  
	}  
	  
	private static class InputProcessor {  
	    private BufferedReader br;  
	    private StringTokenizer st;  
	  
	    public InputProcessor() {  
	        this.br = new BufferedReader(new InputStreamReader(System.in));  
	    }  
	  
	    public String next() {  
	        while (st == null || !st.hasMoreElements()) {  
	            try {  
	                st = new StringTokenizer(br.readLine());  
	            } catch (IOException e) {  
	                throw new RuntimeException(e);  
	            }  
	        }  
	  
	        return st.nextToken();  
	    }  
	  
	    public String nextLine() {  
	        String result = "";  
	  
	        try {  
	            result = br.readLine();  
	        } catch (IOException e) {  
	            throw new RuntimeException(e);  
	        }  
	  
	        return result;  
	    }  
	  
	    public int nextInt() {  
	        return Integer.parseInt(next());  
	    }  
	  
	    public long nextLong() {  
	        return Long.parseLong(next());  
	    }  
	}
}