방화벽 설치하기 (JAVA)

📖 문제

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

 

 

💡  풀이 방식

• 백트래킹 + 가능한 모든 위치에서 한꺼번에 시작하는 BFS

필요 자료구조
- int[][] copy : 원본 배열 값 저장해둘 배열 (얘 대신 boolean[][] visited를 활용해도 된다,,)

- List<int[]> emptyPlaces : 벽 설치 가능한 위치 리스트 ⭐
- List<int[]> realWalls : 벽 있는 위치 리스트 ⭐
- List<int[]> fireList     : 불 있는 위치 리스트 ⭐

- Queue<int[]> q        : 불 위치 저장 큐. BFS 탐색 위해 존재하는 불을 큐에 넣는다.

 

1. 입력 받을 때, 다음과 같이 저장한다.

- 해당 칸이 빈 칸이라면, 나중에 벽을 설치하기 위해 별도의 위치 리스트 emptyPlaces에 해당 좌표를 저장한다. 

- 해당 칸이 "불"이라면, 불의 위치를 담은 리스트 fireList에 해당 좌표를 저장한다. 

 

2. 벽을 설치할 3개의 위치 조합을 뽑기 위해 백트래킹을 수행한다. (파라미터 ⇒ 현재 인덱스, 설치한 벽 개수)

 - 위치 3곳을 정했다면,

     1) 앞에서 만든 방화벽을 제거하고, (초기화 목적)

     2) 선택된 위치 realWalls에 있는 좌표들에 방화벽을 설치하고,

     3) 불이 있는 위치들에서 상하좌우로 불을 퍼지게 하고,

     4) 불이 퍼지지 않은 영역을 구하고, 이를 최댓값과 비교해 갱신한다.

- 아직 위치 3곳을 정하지 못 했다면, 벽 설치 가능한 리스트 emptyPlaces에서 원소를 더 뽑으며 조합을 찾는다.

// 방법1
private static void comb(int idx, int cnt) {
    if(cnt == 3) {
        max = Math.max(max, fire());
        return;
    }

    for(int i = idx ; i < emptyPlaces.size() ; i++) {
        realWalls.add(new int[] {emptyPlaces.get(i)[0], emptyPlaces.get(i)[1]});
        comb(i + 1, cnt + 1);
        realWalls.remove(realWalls.size() - 1);
    }
}

// 방법2
public static void comb(int idx, int cnt) {
    if(cnt == 3) {
        getArea();
        return;
    }

    if(idx == (int) emptyPlaces.size()) 
        return;

	// 현재 값 사용하기
    realWalls.add(idx);
    comb(idx + 1, cnt + 1);
    realWalls.remove(realWalls.size() - 1);

	// 현재 값 skip
    comb(idx + 1, cnt);
}

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N, M;
    static int[][] map;
    static int[][] copy;    // 원본 저장용 배열
    
    static List<int[]> emptyPlaces = new ArrayList<>(); // 벽 설치할 위치 3개 조합 리스트
    static List<int[]> realWalls = new ArrayList<>();   // 벽이 있는 위치 리스트
    static List<int[]> fireList = new ArrayList<>();    // 불이 있는 위치 리스트
 
    static int max = 0; // 불이 퍼지지 않는 영역 크기의 최댓값
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        copy = new int[N][M];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                copy[i][j] = map[i][j];
 
                if(map[i][j] == 0)  emptyPlaces.add(new int[]{i, j});  // 가능한 위치 넣기
                if(map[i][j] == 2)  fireList.add(new int[]{i, j});  // 불 넣기
            }
        }
 
        visited = new boolean[N][M];
        comb(0, 0);
 
        System.out.println(max);
    }
 
    // 불 전파하며 영역 세는 함수
    private static int fire() {
        int[][] tmpMap = new int[N][M];
 
        // 1. 원본 배열 값으로 초기화 (방화벽 제거 목적)
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                tmpMap[i][j] = copy[i][j];
            }
        }
 
        // 2. 선택된 위치에 방화벽 설치하기
        for(int[] w : realWalls) {
            tmpMap[w[0]][w[1]] = 1;
        }
 
        // 3. 불 확산하기
        for(int[] f : fireList) {
            Queue<int[]> q = new ArrayDeque<>();
            q.add(f);
 
            while(!q.isEmpty()) {
                int[] cur = q.poll();
 
                for(int d = 0 ; d < 4 ; d++) {
                    int nx = cur[0] + dx[d];
                    int ny = cur[1] + dy[d];
 
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M)    continue;
 
                    if(tmpMap[nx][ny] == 0) {
                        tmpMap[nx][ny] = 2;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
 
        // 4. 불이 퍼지지 않은 영역 구하기
        int emptyCnt = 0;
        for(int[] i : tmpMap) {
            for(int j : i) {
                if(j == 0) {
                    emptyCnt++;
                }
            }
        }
 
        return emptyCnt;
    }
 
    // 방화벽 세울 위치 3개 조합 구하고 탐색하는 메소드
    private static void comb(int idx, int cnt) {
        if(cnt == 3) {
            max = Math.max(max, fire());
            return;
        }
 
        for(int i = idx ; i < emptyPlaces.size() ; i++) {
            realWalls.add(new int[] {emptyPlaces.get(i)[0], emptyPlaces.get(i)[1]});
            comb(i + 1, cnt + 1);
            realWalls.remove(realWalls.size() - 1);
        }
    }
}

 

 

 

➕ 다른 풀이 방식

visited 방문 배열 활용

- 새 조합에 대해 BFS 탐색할 때마다 visited 배열 초기화해 사용

 

---

💦 어려웠던 점

- 3개 조합 구할 리스트 만들 생각은 했는데 "벽을 세울 수 있는 칸들의 위치를 저장할 리스트"를 만들 생각을 하지 못했다.

- 조합 함수에 어떤 인자를 가져가야 하지 라는 생각을 했다ㅠ

- 불은 어떻게 처리하지? > 일단 불 위치 리스트 fireList에 불 위치를 저장하고 조합에 있는 칸에 방화벽 설치한다. 그리고 반복문으로 fireList 돌면서 bfs로 불을 확산한다.

 

 

 

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

---

(참고)

✔ 코드트리

 

이것도 참고,, 둘다 잘 풀자,,,https://bono039.tistory.com/959