[코드트리/INTERMEDIATE LOW] 돌 잘 치우기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 백트래킹 + BFS

필요 자료구조
- 돌 위치 저장용 리스트 rockList ⭐
- 고른 돌 목록 1차원 int형 배열 (dfs용)
- 방문 표시 배열 (bfs용)
- 시작점 위치 1차원 int형 배열 startPos ⭐

 

1. 격자를 입력받으면서, 돌이 있는 위치를 rockList 리스트에 저장한다.

2.  startPos 배열에 K번 시작점 위치를 저장한다.

3. M개를 뽑는 dfs를 수행한다.

  - 종료 조건 : m개 뽑았을 때

      3-1) 돌을 제거한다.

      3-2) 시작점에서부터 bfs를 수행하여 도달 가능한 칸 수를 구한다.

      3-3) 제거한 돌을 원상복구시킨다.

 

  - 반복문 : 돌이 있는 위치 rockList를 돌며 돌을 m개 뽑는다.

      → 뽑은 돌 정보를 저장하는 배열 res에 뽑은 돌의 인덱스를 저장하고, 다음 인덱스로 넘어가 돌을 뽑도록 한다.

 

4.최대 갯수를 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
 
    static int n, m, k;
    static int[][] map;
    static ArrayList<int[]> rockList = new ArrayList<>();   // 돌 리스트
 
    static int[] res;          // 고른 돌 배열 (dfs용)
    static boolean[][] v;    // 방문 배열 (bfs용)
 
    static int[][] startPos;   // 시작점 위치 저장 배열
 
    static int max = 0;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        res = new int[m];
        map = new int[n][n];
        startPos = new int[k][2];
 
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
 
                if(map[i][j] == 1){
                    rockList.add(new int[]{i , j});
                }
            }
        }
 
        for(int i = 0 ; i < k ; i++){
            st = new StringTokenizer(br.readLine(), " ");
            startPos[i][0] = Integer.parseInt(st.nextToken()) - 1;
            startPos[i][1] = Integer.parseInt(st.nextToken()) - 1;
        }
 
        dfs(0, 0);
        System.out.print(max);
    }
 
    static void dfs(int cur, int depth){
        if(depth == m){
            // 돌 제거하기
            for(int r : res){
                int[] pos = rockList.get(r);
                map[pos[0]][pos[1]] = 0;
            }
 
            v = new boolean[n][n];
            int sum = 0;
 
            for(int[] pos : startPos){
                if(v[pos[0]][pos[1]]) continue;
                sum += bfs(pos[0], pos[1]);
            }
 
            max = Math.max(sum, max);
 
            // 원상복구하기
            for(int r : res){
                int[] pos = rockList.get(r);
                map[pos[0]][pos[1]] = 1;
            }
 
            return;
        }
 
        for(int i = cur ; i < rockList.size() ; i++) {
            res[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
 
    static int bfs(int x, int y){
        Queue<int []> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        
        v[x][y] = true;
        int cnt = 1;
 
        while(!queue.isEmpty()){
            int [] now = queue.poll();
 
            for(int d = 0 ; d < 4 ; d++){
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(!inRange(nx, ny) || v[nx][ny] || map[nx][ny] == 1) continue;
 
                cnt++;
                v[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
        }
        
        return cnt;
    }
 
    static boolean inRange(int x, int y){
        return (0 <= x && x < n && 0 <= y && y < n);
    }
}

 

 

➕ 다른 풀이 방식

[코드트리 챌린지] 돌 잘 치우기

---

💦 어려웠던 점

- 돌 위치를 따로 저장할 리스트를 둘 생각을 하지 못 했다.

- 시작 위치들을 따로 저장해서 사용할 생각을 하지 못 했다.

- 문제를 제대로 읽지 않았다. (각 점에서 최대 방문 가능한 칸의 수 구해서 이 중 최댓값 구하라는 줄,.,)

- 돌을 제거하고, bfs 수행하고 나서 원상복구할 생각을 하지 못 했다.

- 백트래킹 함수에 확신이 없었다,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리