[BOJ 14502] 연구소 (Java, 완전탐색 + 그래프 탐색)

 

---

문제 링크 

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

14502번: 연구소

---

풀이

- 첫번째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

- 0은 빈 칸, 1은 벽, 2는 바이러스 위치

 

아래의 절차와 같이 진행한다

1) 빈칸(0) 위치에 벽을 3개 세운다

2) 바이러스를 전파(방문)한다

3) 바이러스가 전파(방문)하지 않은 빈칸(0) 영역을 카운팅하여 최대 결과값을 찾는다.

 

최대 맵의 크기가 8 * 8 = 64일때 3개의 벽을 찾는 조합의 수 : 64C3 

벽을 3개 세우는 조합을 찾았을 때 2)바이러스 전파와 3)안전 영역 찾는 연산 : 64

 

시간 복잡도 : O(64C3 * 64) = O(41K * 64 ) = O(266만)

 

*개인 기록.
그래프 탐색의 경우 아래 두 가지 유형이 잘 보이고 있음
1) 정점, 간선을 직접 정의하고 탐색 
2) 완전 탐색으로 경우의 수를 찾고 탐색

---

제출 코드

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

public class Main {
    static int N, M, RESULT;

    static int[][] MAP;

    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static void input() 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());

        VISIT = new boolean[N][M];
        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());
            }
        }

        br.close();
    }

    static void bfs() {
        Queue<Integer> que = new LinkedList<>();
		
        // multisource BFS 기법 활용하여 바이러스 위치 담음
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                VISIT[i][j] = false;
                if(MAP[i][j] == 2) {
                    que.add(i);
                    que.add(j);
                    VISIT[i][j] = true;
                }
            }
        }

        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll();

            for(int i = 0; i < 4; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(VISIT[nx][ny]) continue;
                if(MAP[nx][ny] == 0) {
                    que.add(nx);
                    que.add(ny);
                    VISIT[nx][ny] = true;
                }
            }
        }

        int cnt = 0;
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(!VISIT[i][j] && MAP[i][j] == 0) cnt += 1;
            }
        }

        RESULT = Math.max(RESULT, cnt);
    }

    static void dfs(int selectedCount) {
        if(selectedCount == 3) {
            bfs();
            return;
        }

        for(int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(MAP[i][j] == 0) {
                    MAP[i][j] = 1;
                    dfs(selectedCount + 1);
                    MAP[i][j] = 0;
                }
            }
        }
    }

    static void pro() {
        dfs(0);

        System.out.println(RESULT);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}

 

빈칸(0)을 먼저 다 찾아두고 조합을 구할 때 사용하면 메모리와 시간을 낮출 수 있는 방법도 확인