14502번 문제

문제

풀이

요약

1. 벽을 세울 수 있는 모든 경우의 수를 찾는다.
2. 경우의 수에 대해 모든 (2)에 대해서 바이러스를 퍼트리고, 퍼진 구역의 수를 카운팅한다.
3. 바이러스가 퍼진 구역의 수가 가장 적은 값을 정답에 이용한다.

제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,-1,1};
    static List<int[]> blank = new ArrayList<>();
    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];
        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());
                if(map[i][j]==0) blank.add(new int[] {i,j});
            }
        }

        System.out.println(getCntOfMaxSafeArea());
    }

    static int getCntOfMaxSafeArea() {
        int min = Integer.MAX_VALUE;
        for(int i=0; i<blank.size(); i++) {
            int[] one = blank.get(i);
            map[one[0]][one[1]] = 1; // 벽으로 설정
            for(int j=i+1; j<blank.size(); j++) {
                int[] two = blank.get(j);
                map[two[0]][two[1]] = 1;
                for(int k=j+1; k<blank.size(); k++) {
                    int[] three = blank.get(k);
                    map[three[0]][three[1]] = 1;
                    visited = new boolean[N][M];
                    // 바이러스 퍼트리기
                    int sum = getCntOfInfectedArea();
                    if(min > sum) min = sum;
                    map[three[0]][three[1]] = 0;
                }
                map[two[0]][two[1]] = 0;
            }
            map[one[0]][one[1]] = 0;
        }
        return blank.size()-min-3; // 원래 빈 칸 - 감염된 칸 - 새로 세운 벽
    }

    static int getCntOfInfectedArea() {
        int sum = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j]==2 && !visited[i][j]) {
                    visited[i][j] = true;
                    sum += processInfecting(i, j);
                }
            }
        }
        return sum;
    }

    static int processInfecting(int row, int col) {
        int cnt = 0;
        for(int i=0; i<4; i++) {
            int nx = row+dx[i];
            int ny = col+dy[i];

            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;

            if(map[nx][ny]==0 && !visited[nx][ny]) {
                cnt++;
                visited[nx][ny] = true;
                cnt += processInfecting(nx, ny);
            }
        }
        return cnt;
    }
}

우선, 감염되지 않은 구역 중 3곳을 골라서 벽으로 설정하여야 한다.
따라서 List<int[]> blank 자료구조를 통해 빈 곳의 좌표를 리스트 형식으로 저장하였다.

이후 구현은 코드를 보면 알 수 있을 것이다.

• getCntOfMaxSafeArea()
  → 벽을 세우는 모든 경우의 수를 설정하고, getCntOfInfectedArea() 메서드를 호출하여 감염 시나리오를 돌린다.
• getCntOfInfectedArea()
  → 감염된 구역을 찾아내고, processInfecting() 메서드를 호출하여 모든 구역을 감염시킨다. 이후 감염된 모든 구역의 합을 반환한다.
• processInfecting(int row, int col)
  → 해당 좌표를 기준으로 계속해서 상하좌우를 감염시킬 수 있을 만큼(dfs) 감염시킨 뒤, 감염시킨 구역의 수를 반환한다.

---