30. 14502번 연구소

완전 탐색문제

우리가 생각해야할 단계는

1. 벽을 3개 세우고

2. 바이러스를 퍼트린다

3. 안전구역의 갯수를 세어 제일 큰값을 도출한다

가 되겠다

 

각 단계들을 시행하기 위해서는 전제되어야 할점이 있는데

1. 데스나이트 문제와 같이 위치를 특정해줄 Node 객체가 있어야 한다는점

2. 바이러스를 퍼트리는 작업이후 다시 처음 맵으로 돌려서 반복하기 때문에 처음 맵으로 돌리기 위한 복사 과정이 있어야한다는 점

 

Node 객체

static class Node {
        int x, y;

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

x와 y 위치를 가지는 Node객체를 생성

 

 

입력

import java.util.*;
import java.io.*;
static int n;
static int m;
static int[][] map;
static int[][] main_map;
static List<Node> nodeList = new ArrayList<Node>(); // Node객체를 타입으로 가지는 배열
static int[] dx = {1, -1, 0, 0}; // x축 이동
static int[] dy = {0, 0, 1, -1}; // y축 이동
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());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        main_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] == 2)
                    nodeList.add(new Dot(i, j));
            }
        }

        setWall(0, 0);
        System.out.println(max);
    }

setWall = 벽 세우기

벽 세우기 ( 백트래킹 )

static void setWall(int start, int depth) { 
        if (depth == 3) {	// 3번의 진입, 탐색이 끝날시 기존맵으로 복사
            copyMap();
            
            for (Node node : nodeList) { // 배열만큼 반복
                spreadVirus(node.x, node.y);
            }
            // 안전구역 최대값 구하기
            max = Math.max(max, getSafeArea());
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                setWall(i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

copyMap = 제일 처음 아무것도 세우지않은 백지맵으로 되돌리는 작업

spreadVirus = 바이러스를 뿌리는 메소드

getSafeArea = 안전구역의 최대값을 구하는 메소드

 

copyMap 맵 유지

static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                main_map[i][j] = map[i][j];
            }
        }
    }

 

spreadVirus 바이러스 뿌리기

static void spreadVirus(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (main_map[nx][ny] == 0) {
                    main_map[nx][ny] = 2;
                    spreadVirus(nx, ny);
                }
            }
        }
    }

 

getSafeArea 안전구역 최대값 구하기

static int getSafeArea() {
        int safearea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (main_map[i][j] == 0)
                    safearea++;
            }
        }
        return safearea;
    }

 

코드 전문

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

class Main {
    static int n;
    static int m;
    static int[][] map;
    static int[][] main_map;
    static List<Node> nodeList = new ArrayList<Node>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int max = 0;
	
    static class Node {
        int x, y;

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

    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());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        main_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] == 2)
                    nodeList.add(new Node(i, j));
            }
        }

        setWall(0, 0);
        System.out.println(max);
    }


    static void setWall(int start, int depth) {
        if (depth == 3) {   //3개의 벽을 세우고나면 기존맵 복사
            copyMap();
            for (Node node : nodeList) {
                spreadVirus(node.x, node.y);
            }

            // 안전영역 크기 구하기
            max = Math.max(max, getSafeArea());
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                setWall(i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

    static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                main_map[i][j] = map[i][j];
            }
        }
    }

    static void spreadVirus(int x, int y) { //DFS
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (main_map[nx][ny] == 0) {
                    main_map[nx][ny] = 2;
                    spreadVirus(nx, ny);
                }
            }
        }
    }

    static int getSafeArea() {
        int safearea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (main_map[i][j] == 0)
                    safearea++;
            }
        }
        return safearea;
    }
}

결과