[java]연구소 - 백준14502

문제

• 연구소(백준14502)

풀이

문제 해석을 하자면,

• 무조건 3개의 벽을 추가로 쌓고, 바이러스가 없는 안전지대가 가장 많을때를 구하라

풀이

• 먼저 3개의 벽을 세운다.
  • 벽 세우기를 완전탐색으로 간단히 dfs 하였다.
  • 이때 실시간으로 0(빈칸)이 1(벽)으로 바뀌고, 다시 1(벽)이 0(빈칸)으로 바뀌므로
  • 매번 모두 좌표를 확인할 수 있게 2중 for문으로 접근하자.
• 이후 바이러스를 펴트린다.
  • 꼭 visited(방문배열), copyArr(맵 복제한 배열) 을 항상 새로 초기화 하자
  • 이후 바이러스 개수만큼 재귀(dfs)를 돌리면 된다.
  • 이떄 visited로 바이러스가 방문했던 곳은 또 방문안하게 잘 처리하자
• 마지막으로 0(빈칸)의 개수를 세고 답을 도출한다.
  • 이때 맵 복제했던 copyArr로 확인하면 된다.

코드

public static List<Pair> virusArr = new ArrayList<>();
public static int[][] inArr = new int[10][10];
public static boolean[][] visited = new boolean[10][10];
public static int[] dx = {0,1,0,-1};
public static int[] dy = {1,0,-1,0};
public static int N, M, result;

public static void virus(int cx, int cy, int[][] copyArr) {
    //base condition -> visited
    //recursion
    for(int i=0; i<4; i++) {
        int nx = cx+dx[i];
        int ny = cy+dy[i];
        if(nx<0||ny<0||nx>=N||ny>=M) continue;
        if(visited[nx][ny]) continue;
        if(inArr[nx][ny]==0) {
            visited[nx][ny] = true;
            copyArr[nx][ny]=2;
            virus(nx, ny, copyArr);
        }
    }
}

public static void dfs(int depth) {
    //base condition
    if(depth==3) {
        // 2. 바이러스 퍼지기 구현
        // 초기화(visited, copyArr)
        for(int i=0; i<10; i++) for(int j=0; j<10; j++) visited[i][j]=false;
        int[][] copyArr = new int[10][10]; // inArr 바이러스 표시위해 복제!
        for(int i=0; i<10; i++) for(int j=0; j<10; j++) copyArr[i][j] = inArr[i][j];
        // 바이러스 만큼 함수 실행
        for(int i= 0; i<virusArr.size(); i++) {
            Pair p = virusArr.get(i);
            if(visited[p.x][p.y]) continue;
            visited[p.x][p.y]=true;
            copyArr[p.x][p.y]=2;
            virus(p.x, p.y, copyArr);
        }
        // 3. 값 비교 -> '0' 숫자 총 합
        int zeroCnt = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(copyArr[i][j] == 0) zeroCnt++;
            }
        }
        result = Math.max(result, zeroCnt);
        return;
    }
    //recursion
    for(int i=0;i<N;i++) {
        for(int j=0;j<M;j++) {
            if(inArr[i][j]==0) {
                inArr[i][j]= 1;
                dfs(depth+1);
                inArr[i][j]= 0;
            }
        }
    }
}

public static void main(String[] args) throws Exception {
    //init
    for(int i=0; i<10; i++) {
        for(int j=0;j<10;j++) {
            inArr[i][j] = 0;
            visited[i][j] = false;
        }
    }
    result=0;
    virusArr = new ArrayList<>();
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    for(int i=0; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<M; j++) {
            int num = Integer.parseInt(stk.nextToken());
            inArr[i][j] = num;
            if(num==2) virusArr.add(new Pair(i, j));
        }
    }
    //run
    for(int i=0; i<N;i++) {
        for(int j=0; j<M;j++) {
            if(inArr[i][j] == 0) {
                inArr[i][j]= 1;
                dfs(0+1); // 1. 벽 세우기 먼저
                inArr[i][j]= 0;
            }
        }
    }
    //output
    System.out.println(result);
}

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

느낀점

생략