BOJ - 마법사 상어와 복제 23290번 (JAVA)

❓ 문제 - 백준 마법사 상어와 복제 23290번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/23290)

23290번: 마법사 상어와 복제

 

 

📝 문제해결법

1. 이 문제는 DFS(중복조합) + 시뮬레이션으로 문제를 풀었다.

• 문제의 전체적인 흐름은 복제 -> 물고기 이동 -> 상어의 이동 -> 복제마법 이다.
• 전체적인 시뮬레이션 구현을 위해 3중 ArrayList 의 map으로 i행 ,j열에 물고기의 정보(방향)등을 저장한다.
• 처음 물고기 복제를 위해 queue를 통해 현재 map에 존재하는 물고기에 대한 정보를 담아둔다. 
• 물고기 이동할 때 2중 for 문으로 행,열을 접근하면서 물고기 이동 처리를 할 것이기 때문에 map_copy에 이동한 물고기에 대한 정보를 저정하고 다시 map에 정보를 옮겨준다.
• 물고기가 이동할 수 없는 곳이 -> 상어가 존재하는 곳이거나 상어의 냄새가 있는 곳인데. 상어의 냄새는 따로 시간초마다 감소하도록 처리하지 않고, 상어가 물고기를 먹은 곳이라면 smell이라는 2중 배열에 먹었을 때 시간 time을 저장하고, 현재 시간에서 smell에 저장된 숫자를 빼서 2 이하라면 갈 수 없음(냄새가 아직 남았음)으로 처리한다.
• 상어의 이동은 dfs로 중복순열을 통해 순서를 연속된 3방향의 방향을 구하고, 해당 경우일 때 먹을 수 있는 물고기의 수를 카운트해서 최대 먹을 수 있는 물고기 수의 수만큼 먹을 수 있으면 list에 넣어준 후 정렬한다.
• 정렬하면 사전 순으로 정렬이 되므로 0인덱스의 방향으로 상어를 3방향 이동시키고, 만약 물고기 있는 곳으로 이동한다면 물고기의 정보를 없애고 냄새를 남긴다.
• 위에서 queue에 저장한 복제할 정보를 복제마법을 통해 map에 물고기 정보를 넣어준다.
• 계속 반복 후 해당 시간 이후로 남은 물고기 갯수를 출력한다.

2. 물고기 이동

• 해당 map에 물고기의 방향으로 갈 수 없음(상어 존재 or 냄새 존재 or 범위 넘음)면 45도 방향 이동하고, 모든 방향이 다 불가하면 map_copy의 현재 물고기에 위치에 정보를 그대로 넣어준다.

ArrayList<ArrayList<ArrayList<Integer>>> map_copy = new ArrayList<>();
            for(int i=0;i<4;i++){
                map_copy.add(new ArrayList<>());
                for(int j=0;j<4;j++){
                    map_copy.get(i).add(new ArrayList<>());
                }
            }

            for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                    for(int k=0;k<map.get(i).get(j).size();k++){
                        int first_dir =  map.get(i).get(j).get(k);
                        boolean check = true;
                        int nx = i, ny = j;

                        for(int d=0;d<8;d++){
                            int nd = ((first_dir-d)+8) % 8;
                            nx = i + dx[nd];
                            ny = j + dy[nd];
                            if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
                            if(smell[nx][ny] != 0 && time - smell[nx][ny] <= 2) continue;
                            if(nx == s_x && ny == s_y) continue;
                            map_copy.get(nx).get(ny).add(nd);
                            check = false;
                            break;
                        }

                        if(check){
                            map_copy.get(i).get(j).add(first_dir);
                        }

                    }

                }
            }

3. DFS(상어의 3연속 방향의 중복 순열 구하기)

• DFS 방식으로 중복 순열을 구현함
• 만약 depth가 3, 즉 3방향의 한 경우가 만들어지면 eatCount() 함수를 통해 해당 경우일 때 얼만큼 물고기를 먹을 수 있을 지 카운트
• 만약 지금까지 최대 먹을 수 있는 물고기의 수보다 더 많은 수의 물고기를 먹을 수 있다면 moving_list를 clear 한 후 자신의 경우의수를 넣어주고 최대 먹을 수 있는 물고기 수 갱신
• 만약 지금까지 최대 먹을 수 있는 물고기의 수만큼 물고기를 먹을 수 있다면 moving_list에 자신의 경우를 넣어줌

// 상어가 이동할 수 있는 3연속 방향의 중복순열을 구하는 dfs
    public static void dfs(int depth, int[] arr){
        if(depth==3){
            int[] arr_copy = new int[3];
            String str = "";
            for(int i=0;i<3;i++){
                arr_copy[i] = arr[i];
                str += String.valueOf(arr_copy[i]);
            }

            int cnt = eatCount(str);

            if(max_eat < cnt){
                moving_list.clear();
                moving_list.add(Integer.parseInt(str));
                max_eat = cnt;
            } else if (max_eat == cnt){
                moving_list.add(Integer.parseInt(str));
            }

            return;
        }
        for(int i=1;i<=4;i++){
            arr[depth] = i;
            dfs(depth+1, arr);
        }
    }

4. eatCount -> 해당 경우일 때 얼만큼의 물고기를 먹을 수 있는지 카운트하는 함수

• 해당 방향으로 이동하다가 범위를 넘어가면 이동할 수 없는 경우로 취급하면서 리턴
• 어떤 방향으로 갔다가 다시 돌아오는 경우는 한번만 물고기를 먹을 수 있으므로 물고기를 먹었다는 visited 배열을 통해 체크해줌
• 맨 처음에 물고기와 상어가 같이 있는 공간에서 상어의 움직임이 시작될 수 있음(문제 조건) -> 따라서 맨 처음 시작점에서는 물고기를 먹을 수 없지만 어떤 방향으로 갔다가 다시 제자리로 돌아오면 해당 위치의 물고기를 먹을 수 있음

    // 해당 방향으로 3연속 이동할 때 먹을 수 있는 물고기 갯수 카운트
    public static int eatCount(String dir){
        int x = s_x;
        int y = s_y;
        int eat_cnt = 0;
        boolean[][] vistied = new boolean[4][4];

        for(int i=0;i<3;i++){
            int d = dir.charAt(i) - '1';
            x += s_dx[d];
            y += s_dy[d];
            if(x < 0 || y < 0 || x >= 4 || y >= 4){
                return -1;
            }
            if(!vistied[x][y]) eat_cnt += map.get(x).get(y).size();
            vistied[x][y] = true;
        }
        return eat_cnt;
    }

 

5. 느낀점

• 빡구현... 우선 문제를 3번 이상 보면서 문제의 조건을 잘 살피는 게 제일 중요한 것 같다..
• 4번째 깨달은 상어가 이동했다가 다시 제자리로 왔을 때 물고기는 한번만 먹을 수 있음과 처음에 상어와 물고기가 같은 자리에서 상어가 이동할 때는 처음 지점에서 시작부터 먹을 수 없지만 다시 자기 자리로 이동하면 그 땐 먹을 수 있음... -> 이거 엄청 중요한 것 같다... 이것 때문에 65퍼에서 계속 틀렸습니다 뜨고.. 이틀 이상 고민했다...ㅠㅠ 
• 구현은 문제의 조건을 하나하나 다 살피는 것과 내가 구현한 것이 해당 조건에 틀리지 않은지 항상 살피는 능력이 중요한 것 같다...!!!!!!!

 

💻 소스코드

// BOJ - 마법사 상어와 복제(23290번)
// DFS(중복조합) + 시뮬레이션

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_23290 {
    public static int m, s;
    public static int s_x, s_y;
    public static int[][] smell;
    public static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    public static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static ArrayList<ArrayList<ArrayList<Integer>>> map;
    public static ArrayList<Integer> moving_list;
    public static int max_eat;
    public static int[] s_dx = {-1, 0, 1, 0};
    public static int[] s_dy = {0, -1, 0, 1};
    public static class Fish{
        int x;
        int y;
        int d;
        public Fish(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        smell = new int[4][4];
        Queue<Fish> q_first = new LinkedList<>();

        map = new ArrayList<>();
        for(int i=0;i<4;i++){
            map.add(new ArrayList<>());
            for(int j=0;j<4;j++){
                map.get(i).add(new ArrayList<>());
            }
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            map.get(x-1).get(y-1).add(d-1);
        }

        st = new StringTokenizer(br.readLine(), " ");
        s_x = Integer.parseInt(st.nextToken()) -1;
        s_y = Integer.parseInt(st.nextToken()) -1;

        int time = 1;
        while (time<=s){
            // 복제
            q_first.clear();
            for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                    for(int k=0;k<map.get(i).get(j).size();k++){
                        q_first.offer(new Fish(i, j, map.get(i).get(j).get(k)));
                    }
                }
            }

            // 물고기 이동
            ArrayList<ArrayList<ArrayList<Integer>>> map_copy = new ArrayList<>();
            for(int i=0;i<4;i++){
                map_copy.add(new ArrayList<>());
                for(int j=0;j<4;j++){
                    map_copy.get(i).add(new ArrayList<>());
                }
            }

            for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                    for(int k=0;k<map.get(i).get(j).size();k++){
                        int first_dir =  map.get(i).get(j).get(k);
                        boolean check = true;
                        int nx = i, ny = j;

                        for(int d=0;d<8;d++){
                            int nd = ((first_dir-d)+8) % 8;
                            nx = i + dx[nd];
                            ny = j + dy[nd];
                            if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
                            if(smell[nx][ny] != 0 && time - smell[nx][ny] <= 2) continue;
                            if(nx == s_x && ny == s_y) continue;
                            map_copy.get(nx).get(ny).add(nd);
                            check = false;
                            break;
                        }

                        if(check){
                            map_copy.get(i).get(j).add(first_dir);
                        }

                    }

                }
            }

            map = map_copy;

            // 상어의 이동 -> 중복 순열...dfs
            max_eat = 0;
            moving_list = new ArrayList<>();
            dfs(0, new int[3]);
            Collections.sort(moving_list);
            String moving_str = String.valueOf(moving_list.get(0));
                for (int i = 0; i < 3; i++) {
                    int dir = moving_str.charAt(i) - '1';
                    s_x += s_dx[dir];
                    s_y += s_dy[dir];
                    // 죽이면서 냄새 뿌리기
                    if (map.get(s_x).get(s_y).size() > 0) {
                        map.get(s_x).get(s_y).clear();
                        smell[s_x][s_y] = time;
                    }

                }

            // 복제 마법

            while (!q_first.isEmpty()){
                Fish f = q_first.poll();
                map.get(f.x).get(f.y).add(f.d);
            }


            time++;
        }


        // 물고기 갯수 출력
        int ans = 0;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                ans += map.get(i).get(j).size();
            }
        }
        System.out.println(ans);
    }

    // 상어가 이동할 수 있는 3연속 방향의 중복순열을 구하는 dfs
    public static void dfs(int depth, int[] arr){
        if(depth==3){
            int[] arr_copy = new int[3];
            String str = "";
            for(int i=0;i<3;i++){
                arr_copy[i] = arr[i];
                str += String.valueOf(arr_copy[i]);
            }

            int cnt = eatCount(str);

            if(max_eat < cnt){
                moving_list.clear();
                moving_list.add(Integer.parseInt(str));
                max_eat = cnt;
            } else if (max_eat == cnt){
                moving_list.add(Integer.parseInt(str));
            }

            return;
        }
        for(int i=1;i<=4;i++){
            arr[depth] = i;
            dfs(depth+1, arr);
        }
    }

    // 해당 방향으로 3연속 이동할 때 먹을 수 있는 물고기 갯수 카운트
    public static int eatCount(String dir){
        int x = s_x;
        int y = s_y;
        int eat_cnt = 0;
        boolean[][] vistied = new boolean[4][4];

        for(int i=0;i<3;i++){
            int d = dir.charAt(i) - '1';
            x += s_dx[d];
            y += s_dy[d];
            if(x < 0 || y < 0 || x >= 4 || y >= 4){
                return -1;
            }
            if(!vistied[x][y]) eat_cnt += map.get(x).get(y).size();
            vistied[x][y] = true;
        }
        return eat_cnt;
    }
}