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

[ 백준 14502 ] 연구소 ( java )

 

 

출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

 

 

핵심 

1 dfs( y, x, cnt) 를 이용한 벽 세우기 

맵에서 모든 위치를 방문하는데, 벽을 세우거나 세우지 않는다. 

벽을 세우기 위해 값이 0이며 세운 벽의 수가 3개 미만 일 때, 벽을 세운다. 

 

 

+ 두 가지 기저조건

1) cnt현재까지 세운 벽으로, 3개를 세우면 바이러스를 퍼뜨리고, 답을 찾고 dfs를 종료시키면 된다. 

2) 여기서의 dfs는 하나의 (y, x)를 처리하고, 왼쪽에서 오른쪽으로, 오른쪽이 막히면 위에서 아래로 탐색한다. 

따라서, (y, x)의 기저 조건은 y가 N일 때다. 

 

 

 

 

 

 

2 bfs를 이용한 바이러스 퍼뜨리기 

맵 정보를 입력 받을 때, 바이러스 위치를 미리 따로 저장해둔다. 

그리고, 벽 3개를 모두 세웠을 때, 바이러스를 bfs를 이요하여 퍼뜨린다. 

기본적인 bfs인데, visited를 사용안한 이유는 0인 곳에만 방문 후, 바로 2로 바꿨기 때문이다. 

 

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요! 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    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());
        
        origin = new int[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++) {
                origin[i][j] = Integer.parseInt(st.nextToken());
                if(origin[i][j] == 2) {
                    viruses.add(new virus(i, j));
                }
            }
        }
        
        dfs(0, 0, 0);
        System.out.println(max);
    }
    static int N, M;
    static int[][] origin, map;
    
    static ArrayList<virus> viruses = new ArrayList<virus>();
    static class virus{
        int y, x;
        public virus(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    
    static int max = 0;
    static void dfs(int iy, int ix, int cnt) {
        
        if(cnt == 3) {
            Queue<virus> q = new LinkedList<virus>();
            for(int v = 0 ; v < viruses.size() ; v++) {
                q.add(viruses.get(v));
            }
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j< M ; j++) {
                    map[i][j] = origin[i][j];
                }
            }
            
            virus cur;
            int ny, nx;
            while(!q.isEmpty()) {
                cur = q.poll();
                for(int dir = 0 ; dir < 4 ; dir++) {
                    ny = cur.y + delta[dir][0];
                    nx = cur.x + delta[dir][1];
                    if(!(ny>= 0 && ny < N && nx >= 0 && nx < M))
                        continue;
                    if(map[ny][nx] == 0) {
                        map[ny][nx] = 2;
                        q.add(new virus(ny, nx));
                    }
                }
            }
            
            int cntSafe = 0;
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j< M ; j++) {
                    if(map[i][j] == 0)
                        cntSafe++;
                }
            }
            if(max < cntSafe)
                max = cntSafe;
            
            return;
        }
        
        if(iy == N)
            return;
        
        if(origin[iy][ix] == 0 && cnt < 3) {
            origin[iy][ix] = 1;
            if(ix < M-1)
                dfs(iy, ix+1, cnt+1);
            else
                dfs(iy+1, 0, cnt+1);
            origin[iy][ix] = 0;
        }
        if(ix < M-1)
            dfs(iy, ix+1, cnt);
        else
            dfs(iy+1, 0, cnt);
    }
    static int[][] delta = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };
}