[백준] 14502번 / Java / 연구소 - DFS, 완전탐색

문제 - (https://www.acmicpc.net/problem/14502)

완전탐색으로 풀 수 있는 문제였다.

세가지 스텝으로 문제를 해결할 수 있다.

1. 3개의 벽을 세울 수 있는 모든 경우를 구한다.
2. 그 상태에서 바이러스를 퍼뜨리는 시뮬레이션 진행.
3. 진행된 결과를 보고 안전 영역의 갯수를 구한다.

번호 순서대로 내 코드의 dfs, spreadVirus, dfs의 기저부분 함수를 확인하면 된다.

 

---

📌주의할 점

• 벽을 세우는 부분에서 재귀를 이용할 때, 반복문 순회에 주의하자
• 시뮬레이션을 진행할 때, deepCopy를 이용하여 새로운 배열을 만들어 진행해도 괜찮지만 굳이 그럴 필요 없이 전역으로 tempMap배열을 만들어놔서 벽이 세워진 상태의 map을 copy하는 방법을 사용하면 공간복잡도면에서 더 효율적일 수 있다.

---

😅실수

• 벽을 세우는 과정에서 for문을 이용해 재귀로 진입하려고 할 때, i와 j값을 인자로 넘겨주는 아래와 같은 실수를 범했다.

static void dfs(int wall, int x, int y) {
	... 중략 ...
	for (int i = x; i < N; i++) {
		for (int j = y; j < M; j++) { /* j = y로 한 것이 실수 */
			if (map[i][j] != 0) continue;
			map[i][j] = 1;
			dfs(wall + 1, i, j);
			map[i][j] = 0;
		}
	}
}

• 이렇게되면 안되는 이유가, 순회할 때 j를 다 돌아서 i가 1증가하게 되면 j는 0부터 시작해야 하는데 y부터 시작하게 되버린다.
• 따라서 아래와 같이 변경해주어야 한다.

static void dfs(int wall, int x) {
	... 중략 ...
	for (int i = x; i < N; i++) {
		for (int j = 0; j < M; j++) { /* i값 증가시 0부터 시작할 수 있도록 함 */
			if (map[i][j] != 0) continue;
			map[i][j] = 1;
			dfs(wall + 1, i);
			map[i][j] = 0;
		}
	}
}

• 하지만 좀 찜찜한 점이 있다.. 왜냐하면 예를들어 map[0][2]에서 재귀에 진입하면 map[0][3]부터 시작해도 되는데 굳이 map[0][0]부터 다시 시작해버린다. (물론 if문에 의해 continue되겠지만 하지않아도될 연산을 하는 거니까 찜찜하다)
• 여기서 꿀팁등장. 아래와 같은 방법으로 지금 문제를 해결할 수 있다.

for (int i = x; i < N * M; i++) {
	int _x = i / M; // 행
	int _y = i % M; // 열
            
	if (map[_x][_y] == 0) {
		map[_x][_y] = 1;
		dfs(wall + 1, i + 1);
		map[_x][_y] = 0;
	}
}

• 이렇게하면, N=7,M=7이고 i가 7일때, _x=1, _y=0이므로 map[1][0]을 순회할 수 있으며 다음 재귀에서 하지 않아도될 연산을 수행하지 않게 된다.

잊지말고 활용하자

 

---

코드

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


// 골드5 - 55분
public class Laboratory {
    static int N;
    static int M;
    static int[][] map;
    static int answer = Integer.MIN_VALUE;
    static ArrayList<int[]> virusPos;
    static int[][] tempMap;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 이동
    static int[] dy = {0, 0, -1, 1};

    static void dfs(int wall, int x) {
        if (wall == 3) {
            // 바이러스가 퍼져나가는 것 시뮬레이션 하기
            copyMap();
            for (int[] virus : virusPos) {
                spreadVirus(virus[0], virus[1]);
            }

            // 바이러스 퍼진 후의 안전 영역 크기 구하기
            int safeArea = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (tempMap[i][j] == 0) safeArea += 1;
                }
            }

            answer = Math.max(answer, safeArea);
            return;
        }

        for (int i = x; i < N * M; i++) {
            int _x = i / M;
            int _y = i % M;

            if (map[_x][_y] == 0) {
                map[_x][_y] = 1;
                dfs(wall + 1, i + 1);
                map[_x][_y] = 0;
            }
        }
    }

    static void spreadVirus(int x, int y) {
        // 2인 구역을 중심으로 바이러스 전염 시뮬레이션
        for (int dir = 0; dir < 4; dir++) {
            int moveX = x + dx[dir];
            int moveY = y + dy[dir];
            if (moveX < 0 || moveY < 0 || moveX >= N || moveY >= M) continue;
            if (tempMap[moveX][moveY] == 0) {
                tempMap[moveX][moveY] = 2;
                spreadVirus(moveX, moveY);
            }
        }
    }

    static void copyMap() {
        for (int i = 0; i < map.length; i++) {
            tempMap[i] = map[i].clone();
        }
    }

    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];
        tempMap = new int[N][M];
        virusPos = new ArrayList<>();

        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) {
                    virusPos.add(new int[]{i, j});
                }
            }
        }

        dfs(0, 0);

        System.out.println(answer);
    }
}