[Algorithm] 백준_14502 연구소

문제

N*M의 연구소가 있다. 이 연구소의 일부 칸에 2로 표현된 바이러스가 있는데, 이 바이러스는 상하좌우로 퍼져나갈 수 있어서 벽을 세워 바이러스를 막으려고 한다.
벽은 무조건 3개 세워야하고 1로 표현한다. 아무것도 아닌 영역은 0으로 표현되는데, 벽 3개를 다 세우고 바이러스가 퍼져나갔을 때 남는 개수를 출력하면 되는 문제이다.

풀이

분명.. 푸는 방법은 그래도 생각해냈는데 오늘도 코딩하는 게 오래걸렸다... 하루에 하나 푸는 코린이 하이루..

1. 연구소 입력받기
2. 바이러스 위치 ArrayList에 넣어 관리
3. 조합을 이용해 벽을 세우고, DFS를 이용해 바이러스를 퍼뜨린다.
4. 0의 값을 세고 출력한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_14502 {
    static int M, N;
    static int[][] map;
    static int[][] mapClone;
    static ArrayList<Point> virus = new ArrayList<>();
    static int maxNum = 0;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 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];
        mapClone = 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 ) {
                    virus.add(new Point(i, j));
                }
            }
        }

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

    public static void setWall(int x, int y, int depth) {
        if (depth == 3) {
            //벽을 세운 상태를 copy 해야하기 때문에 clone 안하고 복사합니다
           copyMap();

            for(Point p : virus) {
                dfs(p.x, p.y);
            }

            maxNum = Math.max(maxNum, getArea());
            return;
        }

        for(int i= x; i < N; i++) {
            for(int j=0; j<M; j++) {
                if( i == x && j < y ) {
                    continue;
                }
                System.out.println(i+"," +j);
                if(map[i][j] == 0) {
                    map[i][j] =1;
                    setWall(i, j+1,  depth + 1);
                    map[i][j] =0;
                }
            }

        }
    }

    public static void copyMap() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                mapClone[i][j] = map[i][j];
            }
        }
    }

    public static int getArea() {
        int count =0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (mapClone[i][j] == 0) {
                    count++;
                }
            }
        }
        return count;
    }

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

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (mapClone[nx][ny] == 0) {
                    mapClone[nx][ny] = 2;
                    dfs(nx, ny);
                }
            }
        }
    }

    static class Point {
        int x, y;

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

후기 😷

가로 세로가 XY좌표 - 행렬은 다르다는거 자꾸 헷갈린다. 주의하자..

그리고 조합 부분은 하다가 모르겠어서 찾아봤다. 결국 서치해서 백트래킹을 사용했다.
백트래킹은 완전탐색을 하는 과정에서, 조건에 부합하지 않으면 다시 이전의 상태로 되돌아가 다시 서치하는 알고리즘이다.

+++ 추가

JAVA의 깊은 복사와 얕은 복사

깊은 복사 : 값 자체만 복사하는 것. 한 배열을 수정해도 다른 배열에 영향을 미치지 않는다.
--> 2차원 배열의 경우 이중 for문을 순회하며 복사하는 방법이 있다.
1차원 배열은 clone()을 사용해주면 간단히 가능👌
객체 배열의 경우는 객체의 주소값을 가지고 있어서 깊은 복사가 안된다.

얕은 복사 : 객체의 주소값이 복사된다. 그래서 한 배열을 수정하면, 다른 배열도 같이 수정된다.