백준 14502

https://www.acmicpc.net/problem/14502

구현문제이다.

package 구현;

import java.io.*;
import java.util.*;

public class Main {

    static int[][] map;
    static int N;
    static int M;
    static ArrayList<int[]> arr0 = new ArrayList<>();
    static ArrayList<int[]> arr2 = new ArrayList<>();
    static int[] dx = new int[] {1,-1,0,0};
    static int[] dy = new int[] {0,0,1,-1};
    static int[][] newMap;

    static int ans = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        newMap = new int[N][M];
        for (int i = 0; i < N; i++) {

            String[] arr = br.readLine().split(" ");

            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(arr[j]);
                if(map[i][j] == 0){
                    arr0.add(new int[] {i,j});
                }
                else if(map[i][j] == 2){
                    arr2.add(new int[] {i,j});
                }
            }
        }
        createWall();

        System.out.println(ans);

    }

    public static void createWall(){
        for (int i = 0; i < arr0.size() - 2; i++) {
            for (int j = i+1; j < arr0.size() - 1; j++) {
                for (int k = j+1; k < arr0.size(); k++) {
                    for(int a = 0;a<N;a++){
                        newMap[a] = map[a].clone();
                    }

                    int[] arrA = arr0.get(i);
                    int[] arrB = arr0.get(j);
                    int[] arrC = arr0.get(k);

                    newMap[arrA[0]][arrA[1]] = 1;
                    newMap[arrB[0]][arrB[1]] = 1;
                    newMap[arrC[0]][arrC[1]] = 1;

                    score();

                }
            }
        }
    }

    public static void score(){
        int score = 0;
        for (int[] ints : arr2) {
            DFS(ints);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(newMap[i][j] == 0){
                    score ++;
                }
            }
        }

        ans = Math.max(ans,score);

    }

    public static void DFS(int[] arr2){
        for (int i = 0; i < 4; i++) {
            if(0<=arr2[0]+dx[i] && arr2[0]+dx[i]<N && 0<=arr2[1]+dy[i] && arr2[1]+dy[i]<M) {
                if(newMap[arr2[0]+dx[i]][arr2[1]+dy[i]] == 0){
                    newMap[arr2[0]+dx[i]][arr2[1]+dy[i]] = 2;
                    DFS(new int[] {arr2[0]+dx[i],arr2[1]+dy[i]});
                }
            }
        }

    }
}

처음에 바로 풀었을떈 여러개의 좌표중 벽 3개를 고르는 알고리즘을 단순 for문으로 했는데 이는 고르는 개수가 늘수록 시간복잡도상 손해이다.

조합

N 개중 중복되지 않은 K개의 수를 고를땐 DFS를 이용해서 풀자

이 문제에선 3개를 고르는 것이니까 DFS 관점에서 Depth가 3이될때까지 map을 update 하면 된다.

  public static void createWall(int depth){
        if(depth == 3){
            score();
            return;
        }

        for (int i = 0; i < N; i++) {
            for(int j = 0;j < M; j++){
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    createWall(depth+1);
                    map[i][j] = 0;
                }
            }
        }
    }

createWall 부분을 위의 방법으로 수정하여 더 범용적으로 사용할 수 있고 코드도 간결해졌다.

하지만 이러면 for문을 계속 0부터 돌리므로 탐색했던 부분을 또 하는 문제가 있다.

->1차원 배열로 변환하여 탐색했던 곳은 가지 않기(백트래킹)

  public static void createWall(int depth,int start){
        if(depth == 3){
            score();
            return;
        }

        for(int i = start; i < N*M; i++){
            if(map[i/M][i%M] == 0){
                map[i/M][i%M] = 1;
                createWall(depth+1,i+1);
                map[i/M][i%M] = 0;
            }
        }
    }

바이러스 퍼지는 코드도 1차원 배열로 수정할 수도 있다.

public static void DFS(int n){
        for (int i = 0; i < 4; i++) {
            int x = n/M+dx[i];
            int y = n%M+dy[i];
            if(0<=x && x<N && 0<=y && y<M) {
                if(newMap[x][y] == 0){
                    newMap[x][y] = 2;
                    DFS(x*M+y);
                }
            }
        }

    }

2차원 배열 복사

java에선 1차원 깊은 배열복사는 clone()을 이용하면 된다.

int[] a = new int[] {1,2,3};
int[] b= a.clone();

하지만 2차원에선 똑같이 구현하면 얕은복사가 되므로 for문을 통해 구현해야한다.

2차원 배열 깊은 복사

int[][] a = new int[][] {{1,2,3},{1,2,3}};
int[][] b = new int[2][3];

for(int i = 0; i < a.size(); i++){
	b[i] = a[i].clone();
}