[JAVA/DFS] 백준 19236 청소년 상어

1. 문제

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

19236번: 청소년 상어

 

2. 풀이

• 상어의 위치를 DFS를 이용해 움직인다.
• 상어와 물고기를 각각 객체를 만들어 사용한다.
  • 물고기(Fish)는 좌표, 물고기 번호, 방향, 살아있는지 여부를 멤버 변수로 갖는다.
  • 상어(Shark)는 좌표, 방향, 먹은 물고기 번호의 합을 멤버 변수로 갖는다.
• 물고기 번호를 입력 받고, 탐색을 시작하기전,
  • 물고기를 번호 순서대로 먹기 위해 물고기가 담긴 list를 번호순으로 오름차순 정렬한다
  • 상어가 (0,0)로 이동해 (0,0)에 있는 물고기를 먹는다.
• DFS로 물고기를 이동하는데 먼저 모든 살아있는 물고기들을 이동한다(moveFish())
  • 반시계방향으로 이동하기 위해 이동 좌표를 담은 배열 dir에 반시계방향으로 값을 넣는다.
• 상어가 해당 방향으로 1칸 이상 이동할 수 있기 때문에 for문을 이용해 최대 3배수까지 움직인다.
• 먹히거나 상어가 있는 자리는 지나지 않는다.
  • map[i][j] == 0 : 먹힌 자리
  • map[i][j] == -1: 상어가 있는 자리
• 먹을 수 있는 물고기를 먹고, 계속해서 DFS를 진행해 먹을 수 있는 물고기 번호 합의 최댓값을 구한다

 

3. 코드

 

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

class Main{
    
    // 청소년 상어
    
    static class Fish { // 물고기
        int x, y, number, dir;
        boolean isAlive; // 상어에게 먹히지 않고 살아있는지
        
        public Fish(int x, int y, int number, int dir, boolean isAlive) {
            this.x = x;
            this.y = y;
            this.number = number;
            this.dir = dir;
            this.isAlive = isAlive;
        }
        
        public Fish() {}
    }
    
    static class Shark{ // 상어
        int x, y, dir, sum; // 좌표, 방향, 먹은 물고기 번호 합
        
        public Shark(int x, int y, int dir, int sum) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.sum = sum;
        }
    }
    
    // 반시계방향
    static int[][] dir = {{-1,0},{-1,-1},{0,-1},{1,-1},
                            {1,0},{1,1},{0,1},{-1,1}};
    static int max = 0;
    
    // 주어진 좌표가 map 범위 내인지
    public static boolean isInRange(int x, int y) {
        return (x >= 0 && x < 4 && y >= 0 && y < 4);
    }
    
    public static int[][] copyMap(int[][] map) {
        int[][] tmp = new int[4][4];
        
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                tmp[i][j] = map[i][j];
        
        return tmp;
    }
    
    public static ArrayList<Fish> copyList(ArrayList<Fish> fishes){
        ArrayList<Fish> tmp = new ArrayList<Fish>();
        fishes.forEach(e -> tmp.add(new Fish(e.x, e.y, e.number, e.dir, e.isAlive)));
        return tmp;
    }
    
    // 빈 칸 또는 다른 물고기 있는 칸으로 물고기 이동
    public static void moveFish(Fish f, int[][] map, ArrayList<Fish> fishes) {
        
        if(f.isAlive == false) return;
        
        for(int i = 0; i < 8; i++) {
            int nDir = (f.dir + i) % 8;
            int nX = f.x + dir[nDir][0];
            int nY = f.y + dir[nDir][1];
            
            // 상어 있는 자리는 지나지 않음
            if(!isInRange(nX, nY) || map[nX][nY] == -1) continue;
            
            map[f.x][f.y] = 0;
            
            if(map[nX][nY] == 0) { // 빈 자리면 바로 이동
                f.x = nX;
                f.y = nY;
            }else { // 빈자리 아니면 다른 물고기와 변경
                Fish tmp = fishes.get(map[nX][nY] - 1);
                tmp.x = f.x;
                tmp.y = f.y;
                map[f.x][f.y]= tmp.number;
                
                f.x = nX;
                f.y = nY;
            }
            
            map[nX][nY] = f.number;
            f.dir = nDir;
            return;
        }
    }
    
    // dfs를 통해 상어 이동
    public static void dfs(int[][] map, ArrayList<Fish> fishes, Shark shark) {
        
        if(max < shark.sum) {
            max = shark.sum;
        }
        
        // 모든 살아있는 물고기 이동
        fishes.forEach(e -> moveFish(e, map, fishes));
        
        // 4*4이므로 최대 3배수까지 움직일 수 있음
        for(int i = 1; i < 4; i++) {
            int nX = shark.x + dir[shark.dir][0] * i;
            int nY = shark.y + dir[shark.dir][1] * i;
            
            // 먹히거나 상어 있는 자리는 지나지 않음
            if(!isInRange(nX, nY) || map[nX][nY] <= 0) continue;
            
            // 물고기 잡아먹고 dfs 계속
            int[][] cMap = copyMap(map);
            ArrayList<Fish> cFishes = copyList(fishes);
            
            Fish eatenFish = cFishes.get(map[nX][nY] - 1); // 물고기 잡아 먹음
            cMap[shark.x][shark.y] = 0; 
            eatenFish.isAlive = false;
            cMap[eatenFish.x][eatenFish.y] = -1;  // 새로운 상어 위치
            Shark nShark = new Shark(eatenFish.x, eatenFish.y, eatenFish.dir, shark.sum + eatenFish.number);
            
            dfs(cMap, cFishes, nShark);
            
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[][] map = new int[4][4];
        ArrayList<Fish> fishes = new ArrayList<>();

        for(int i = 0; i < 4; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 4; j++) {
                Fish f = new Fish();
                f.number = Integer.parseInt(st.nextToken());
                f.dir = Integer.parseInt(st.nextToken()) - 1;
                f.x = i;
                f.y = j;
                f.isAlive = true;
                map[i][j] = f.number;
                fishes.add(f);
            }
        }
        
        // 물고기를 번호순으로 오름차순 정렬
        Collections.sort(fishes, new Comparator<Fish>() {
            @Override
            public int compare(Fish f1, Fish f2) {
                return f1.number - f2.number;
            }
        });
        
        // 상어가 (0,0) 위치의 물고기를 먹음
        Fish f = fishes.get(map[0][0] - 1);
        f.isAlive = false;
        map[f.x][f.y] = -1; // 상어 위치
        Shark shark = new Shark(0, 0, f.dir, f.number);
        dfs(map, fishes, shark);
        
        System.out.println(max);
    }
}