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

코드트리 실력진단

느낀점

DP문제에서 막혀서 더 못풀었다 ㅠㅠ 이번에 자신있었는데..
열심히 공부해서 다음주 진단에는 600점 이상 받을 수 있도록 노력하려고한다.

문제

https://www.codetree.ai/cote/14/problems/clear-stones-well?&utm_source=clipboard&utm_medium=text

풀이 방법

• 백트래킹 알고리즘을 사용하여 m개의 돌을 뽑았을 때의 위치를 list에 기록
• m개의 돌을 뽑았을 때 기록한 list를 기반으로 새로운 new_map을 만들어주고 map과 똑같이 deep copy를 하되, 돌을 치운 위치는 0으로 바꿔주고 시작위치는 2를 넣어줌
• Queue와 BFS 알고리즘을 사용하여 시작점에서 갈 수 있는 위치를 2로 바꿔준 후 new_map을 돌면서 갈 수 있는 위치의 개수를 세어줌
• 최댓값 갱신

코드

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

public class Main {
    static int n, m, k;
    static int[] dx = {0, 0, -1, 1}; // 상하좌우 4가지 방향
    static int[] dy = {1, -1, 0, 0};
    static int[][] map;
    static ArrayList<Pair> stoneList; // 돌 위치 기록 리스트
    static ArrayList<Pair> list; // 뽑은 돌의 위치 기록 리스트
    static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stk.nextToken());
        k = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        map = new int[n + 1][n + 1];
        stoneList = new ArrayList<>(); // 주어진 돌의 위치 기록
        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 1) {
                    stoneList.add(new Pair(i, j));
                }
            }
        }

        list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());

            map[x][y] = 2; // 시작점 기록
        }

        backtracking(m, 0);
        System.out.println(ans);
    }

    private static void backtracking(int m, int count) {
        if (count == m) { // m개의 돌을 고른 후 탐색
        	// 최댓값 갱신
            ans = Math.max(ans, bfs());
            return;
        }
        for (int i = 0; i < stoneList.size(); i++) {
            list.add(stoneList.get(i));
            backtracking(m, count + 1);
            list.remove(list.size() - 1);
        }
    }

    private static int bfs() {
        Queue<Pair> q = new LinkedList<>();
        int[][] new_map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                new_map[i][j] = map[i][j];
                if (new_map[i][j] == 2) { // 시작위치를 큐에 삽입
                    q.offer(new Pair(i, j));
                }
            }
        }

        for (int i = 0; i < list.size(); i++) {
            Pair cur = list.get(i); // 뽑은 돌의 위치를 new_map에서 0으로 바꿔줌(돌을 치움)
            new_map[cur.x][cur.y] = 0;
        }

        while (!q.isEmpty()) { // 탐색
            Pair cur = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if (nx <= 0 || ny <= 0 || nx > n || ny > n) {
                    continue;
                }
                // 방문했거나 돌이 있으면 넘어감
                if (new_map[nx][ny] == 2 || new_map[nx][ny] == 1) { 
                    continue;
                }
                q.offer(new Pair(nx, ny));
                new_map[nx][ny] = 2; // 방문 기록
            }
        }

		// 탐색할 수 있는 지점 세기
        int count = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (new_map[i][j] == 2) {
                    count++;
                }
            }
        }
        return count;
    }
}

#코드트리 #코딩테스트 #코딩테스트실력진단