[백준/JAVA] 14502번: 연구소

📖 문제

14502번: 연구소

 

 

 

💡  풀이 방식

• DFS + BFS + 브루트포스

 

 

1. 입력을 받으면서 빈 칸의 위치와 바이러스의 위치를 리스트에 저장해둔다.

- 빈 칸 위치 저장한 이유 : 빈 칸 위치들 중 3개만 뽑으려고 할 때 완전탐색으로 모든 빈 칸 위치 안 찾으려고

- 바이러스 위치 저장한 이유 : 완전탐색으로 바이러스 위치 안 찾으려고

 

 

2. 빈 칸 중 3개를 뽑아 벽을 세우고, 바이러스를 퍼뜨린다.

  2-1) 빈 칸 중 3개 뽑는 방법 : DFS

private static void dfs(int idx, int cnt) {
    if(cnt == 3) {  // 벽 3개 세웠을 때
        setWalls();
        virus();
        getSafeZone();
        return;
    }

    for(int i = idx ; i < emptyList.size() ; i++) {
        if(!dfsVisited[i]) {
            dfsVisited[i] = true;
            dfs(i + 1, cnt + 1);
            dfsVisited[i] = false;
        }
    }
}

 

 

  2-2)  뽑은 3칸에 벽을 세운다. 이 때는 원본 배열이 아닌 원본 배열의 값을 복사한 임시 배열을 활용해 벽을 세운다.

private static void setWalls() {
    // 원본 배열 복사 (.clone()하면 X)
    tmp = new int[N][M];
    for(int i = 0 ; i < N ; i++) {
        for(int j = 0 ; j < M ; j++)
            tmp[i][j] = map[i][j];
    }

    // 선택된 벽 (disVisited == true)에 대해 벽 세우기
    for(int i = 0 ; i < dfsVisited.length ; i++) {
        if(dfsVisited[i]) {
            tmp[emptyList.get(i)[0]][emptyList.get(i)[1]] = 1;
        }
    }
}

 

 

 

  2-3)  임시 배열의 값을 활용해 바이러스를 퍼뜨린다.

private static void virus() {
    visited = new boolean[N][M];

    for(int[] now : virusList) {
        if(!visited[now[0]][now[1]]) {  // 방문한 적 없는 바이러스를 퍼뜨릴 대상에 추가
            visited[now[0]][now[1]] = true;
            q.add(new int[]{now[0], now[1]});
        }
    }

    bfs();  // 퍼뜨리기
}

private static void bfs() {
    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0 ; d < 4 ; d++) {  // 인접한 4방향 퍼뜨리기
            int nx = now[0] + dx[d];
            int ny = now[1] + dy[d];

            // 격자 범위 벗어나면 pass
            if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;

            // 방문한 적 없는 빈 칸에 바이러스 퍼뜨리기
            if(!visited[nx][ny] && tmp[nx][ny] == 0) {
                visited[nx][ny] = true;
                tmp[nx][ny] = 2;
                q.add(new int[]{nx, ny});
            }
        }
    }
}

 

 

 

  2-4)  안전영역 수를 구하고, 이를 최댓값과 비교해 더 큰 값으로 갱신한다.

private static void getSafeZone() {
    int cnt = 0;

    for(int i = 0 ; i < N ; i++) {
        for(int j = 0 ; j < M ; j++) {
            if(tmp[i][j] == 0)
                cnt++;
        }
    }

    answer = Math.max(answer, cnt); // 최대 안전영역 수 갱신
}

 

 

 

💥 유의사항

2차원 객체 배열을 복사할 때 .clone()하면 복사가 안 된다. 유의하자,, (참고)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static int[][] map, tmp;
    
    static List<int[]> emptyList = new ArrayList<>();   // 빈 칸(0) 목록
    static boolean[] dfsVisited;    // 빈 칸 뽑기용
    
    static List<int[]> virusList = new ArrayList<>();   // 바이러스 리스트
    
    static int answer = 0;
    
    static Queue<int[]> q = new ArrayDeque<>();
    static boolean[][] visited;
    
    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];
        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] == 0)
                    emptyList.add(new int[]{i, j});
                else if(map[i][j] == 2)
                    virusList.add(new int[]{i, j});
            }
        }
        
        dfsVisited = new boolean[emptyList.size()];
        dfs(0, 0);
        System.out.println(answer);
    }
    
    // 벽 3개 세우고, 바이러스 퍼뜨리기
    private static void dfs(int idx, int cnt) {
        if(cnt == 3) {  // 벽 3개 세웠을 때
            setWalls();
            virus();
            getSafeZone();
            return;
        }
        
        for(int i = idx ; i < emptyList.size() ; i++) {
            if(!dfsVisited[i]) {
                dfsVisited[i] = true;
                dfs(i + 1, cnt + 1);
                dfsVisited[i] = false;
            }
        }
    }
    
    // 벽 세우기
    private static void setWalls() {
        // 원본 배열 복사 (.clone()하면 X)
        tmp = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++)
                tmp[i][j] = map[i][j];
        }
        
        // 선택된 벽 (disVisited == true)에 대해 벽 세우기
        for(int i = 0 ; i < dfsVisited.length ; i++) {
            if(dfsVisited[i]) {
                tmp[emptyList.get(i)[0]][emptyList.get(i)[1]] = 1;
            }
        }
    }
    
    // 바이러스 퍼뜨리기
    private static void virus() {
        visited = new boolean[N][M];
        
        for(int[] now : virusList) {
            if(!visited[now[0]][now[1]]) {  // 방문한 적 없는 바이러스를 퍼뜨릴 대상에 추가
                visited[now[0]][now[1]] = true;
                q.add(new int[]{now[0], now[1]});
            }
        }
        
        bfs();  // 퍼뜨리기
    }
    
    private static void bfs() {
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {  // 인접한 4방향 퍼뜨리기
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;
                
                if(!visited[nx][ny] && tmp[nx][ny] == 0) {  // 방문한 적 없는 빈 칸에 퍼뜨리기
                    visited[nx][ny] = true;
                    tmp[nx][ny] = 2;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
    
    // 안전영역 수 구하기
    private static void getSafeZone() {
        int cnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(tmp[i][j] == 0)
                    cnt++;
            }
        }
        
        answer = Math.max(answer, cnt); // 최대 안전영역 수 갱신
    }
}

 

 

 

➕ 다른 풀이 방식

 

[백준 14502] - 연구소 자바(JAVA)

[백준] 14502번 : 연구소 - 자바[Java]

모든 것을 완전탐색으로 해결한 풀이 (내 코드보다 메모리는 2배, 시간은 1.5배 가량 더 걸림)

- 방문 배열 사용하지 않으셨음.

- 완전탐색으로 매번 빈 칸(0) 위치 찾아서 dfs했고, 완전탐색으로 바이러스 위치 찾아 bfs하셨음

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static int[][] map, tmp;
    static Queue<int[]> q = new ArrayDeque<>();
    
    static int answer = 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];
        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());
            }
        }
        
        dfs(0);
        System.out.println(answer);
    }
    
    private static void dfs(int cnt) {
        if(cnt == 3) {  // 벽 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(cnt + 1);
                    map[i][j] = 0;
                }                
            }
        }
    }
    
    private static void bfs() {
        // 완전탐색으로 바이러스 위치 찾아 큐에 추가
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 2)
                    q.add(new int[]{i, j});
            }
        }
        
        // 원본 배열 복사
        tmp = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++)
                tmp[i][j] = map[i][j];
        }
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;
                
                if(tmp[nx][ny] == 0) {
                    tmp[nx][ny] = 2;
                    q.add(new int[]{nx, ny});
                }
            }
        }
        
        getSafeZone();
    }
    
    private static void getSafeZone() {
        int cnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(tmp[i][j] == 0)
                    cnt++;
            }
        }
        
        answer = Math.max(answer, cnt);
    }
}
 

 

---

💦 어려웠던 점

- 30분 풀고... 30분 디버깅,,,

- 2차원 배열 clone()해서 값 가져오려고 했더니 복사가 안 됐다. 이것 때문에 20분 정도 헤맨 듯ㅠ

 

 

🧐 새로 알게 된 내용

- 칸에 들어있는 숫자에 따라 방문 여부를 판단 가능하므로 굳이 방문 배열을 사용할 필요가 없다!

- 2차원 배열을 복사할 때는 그냥 무조건 완탐으로 값 복사해주자..

 

 

1회독	2회독	3회독	4회독	5회독
V