[코드트리/BFS] 돌 잘 치우기

문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-clear-stones-well/description?page=1&page_size=20

Code Tree | Learning to Code with Confidence

 

해결방법

해당 문제를 해결하기 위해서는 돌 치우는 경우의 수 구현, BFS로 각 시작점에서부터 도달 가능한 칸의 수 탐색 두가지 구현이 필요하다.

첫번째로 돌 치우는 경우의 수는 입력값 K차수의 경우의수를 구해야하기때문에, 일반적인 N차 반복문으로 구현하기 어렵다. 그러므로 재귀 함수를 사용하여 조합 경우의 수를 구현하였고, 재귀함수에는 아래의 내용으로 작성하였다.

• 인덱스 값으로 i 번째 자리에 대한 경우의 수를 표현한다.
  • 조합을 구현하는 방법을 모르는 경우 아래의 게시글을 참고
  • https://minhamina.tistory.com/38
• 돌 리스트를 순회 (현재 idx + 1 ... list.size())
  • 입력처리할때 map[i][j]의 값이 1인 경우를 리스트에 미리 저장한다.
  • 해당 방법을 통해 돌의 위치를 매번 계산하지 않아도 되어 시간복잡도를 O(N^2) -> O(돌의 개수)로 감소시킬 수 있다.
• 인덱스 값 == M이 되는 경우 돌을 치운 상태의 맵을 생성하여 bfs메소드 호출

두번째로 BFS메소드는 일반적인 While문과 Queue를 사용하는 방법으로 구현하면 된다. 이때, 각 시작점에서 접근 가능한 칸의 수를 계산하는 문제이므로, cnt변수와 visited배열을를 매번 초기화하는것이 아닌, 누적시켜야한다.

소스코드

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

class Position{
    int x, y;
    public Position(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int N, K, M;
    static int[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static List<Position> stoneList = new ArrayList<>();
    static List<Position> startPosition = new ArrayList<>();
    static int answer = 0;

    public static void main(String[] args) throws IOException{
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        K = Integer.parseInt(first[1]);
        M = Integer.parseInt(first[2]);
        map = new int[N][N];
        for(int i = 0; i < N; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(line[j]);
                if(map[i][j] == 1)
                    stoneList.add(new Position(j, i));
            }
        }
        for(int i = 0; i < K; i++){
            String[] line = br.readLine().split(" ");
            Position p = new Position(Integer.parseInt(line[1]) - 1, Integer.parseInt(line[0]) - 1);
            startPosition.add(p);
        }

        solve(0, -1, new Position[M]);

        System.out.println(answer);
        
    }

    static void solve(int sNum, int nIdx, Position[] selected){
        if(sNum == M){
            for(int i = 0; i < M; i ++){
                map[selected[i].y][selected[i].x] = 0;
            }
            // bfs 실행
            int cnt = bfs();
            if(cnt > answer)
                answer = cnt;
            for(int i = 0; i < M; i ++){
                map[selected[i].y][selected[i].x] = 1;
            }

            return;
        }

        for(int i = nIdx + 1; i < stoneList.size(); i++){
            selected[sNum] = stoneList.get(i);
            solve(sNum + 1, i, selected);
        }
    }

    static int bfs(){
        int result = 0;
        int[][] visited = new int[N][N];
        for(Position start : startPosition){
            if(visited[start.y][start.x] == 1)
                continue;
            Queue<Position> queue = new LinkedList<>();
            queue.add(start);
            visited[start.y][start.x] = 1;
            while(!queue.isEmpty()){
                Position now = queue.poll();
                result++;
                for(int i = 0; i < 4; i++){
                    Position next = new Position(now.x + dx[i], now.y + dy[i]);
                    if(next.x < 0 || next.x >= N || next.y < 0 || next.y >= N)
                        continue;
                    if(visited[next.y][next.x] == 1 || map[next.y][next.x] == 1)
                        continue;
                    
                    visited[next.y][next.x] = 1;
                    queue.add(next);
                }
            }
        }

        return result;
    }
}