[BOJ] 14502. 연구소(DFS, DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

이 문제를 해결하기 위해 전체적으로 세 단계로 나뉘어진다.

1. 3개의 벽을 설치하기

2. 바이러스 퍼뜨리기

3. 안전영역 크기 구하기

#. Code_v2

나름의 최적화..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

import java.awt.Point; 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 BOJ14502_v2 {          static int N, M, wallCnt = 0, res = 0, map[][];     static boolean visited[][];     static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};     static Queue<Point> q;     static ArrayList<Point> virus;          public static void setupWall(int cnt) {         // 벽을 세 개 모두 설치했다면         if(cnt == 3) {             // 바이러스를 퍼뜨려보자.             spreadVirus();             return;         }                      for (int i = 0; i < N*M; i++) {             // 빈 칸일 경우             if(map[i/M][i%M] == 0) {                 // 벽을 세워볼까                 map[i/M][i%M] = 1;                 setupWall(cnt+1);                 // 벽을 그냥 안 세울래                 map[i/M][i%M] = 0;             }         }     }          public static void spreadVirus() {         int virusCnt = 0;         visited = new boolean[N][M];         q = new LinkedList<>();         // 바이러스의 좌표들을 하나씩 확인하면서         for (int i = 0; i < virus.size(); i++) {             Point v = virus.get(i);             // Queue에 넣어주고             q.add(new Point(v.x, v.y));             // 바이러스를 퍼뜨려보자.             while(!q.isEmpty()) {                 Point now = q.poll();                                  for (int d = 0; d < 4; d++) {                     int xx = now.x + dx[d];                     int yy = now.y + dy[d];                     // 범위를 벗어나면 pass                     if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;                     // 빈곳이 아니거나 이미 방문한 곳이면 pass                     if(map[xx][yy] != 0 || visited[xx][yy]) continue;                     // 빈 칸이면 바이러스로 감염시키고 Queue에 add                     visited[xx][yy] = true;                     virusCnt++;                     q.add(new Point(xx,yy));                 }             }         }         // 바이러스가 모두 퍼졌을 때, 안전 영역의 크기를 count         res = Math.max(res, (N * M) - wallCnt - 3 - virusCnt - virus.size());     }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  st = new StringTokenizer(br.readLine(), " ");         N = Integer.parseInt(st.nextToken());    // 세로         M = Integer.parseInt(st.nextToken());    // 가로         map = new int[N][M];         virus = 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] == 1) wallCnt++;                 // 바이러스의 위치 저장                 if(map[i][j] == 2) virus.add(new Point(i, j));             }         }                  // 재귀로 3개의 벽을 설치해보자.         setupWall(0);           System.out.println(res);     } }   Colored by Color Scripter

cs

line 85) 초기 벽의 개수를 카운트(안전 영역 크기를 구하는데 사용)

line 87) 바이러스 위치 저장(안전 영역 크기 구하는데와 바이러스를 퍼뜨리는데 사용)

line 18~36) 벽을 세우는 setupWall 함수

line 20) 3개의 벽을 모두 설치했다면

line 22) 바이러스를 퍼뜨리고 안전 영역의 크기를 구해야 한다

line 26~35) Map을 돌면서 해당 좌표에 벽을 세웠을 경우와 세우지 않았을 경우를 확인

line 38~67) 바이러스를 퍼뜨리고 안전 영역의 크기를 구하는 함수

line 43~64) 바이러스의 좌표들을 하나씩 확인하면서

line 48~63) 바이러스를 퍼뜨려나아가자

line 66) 바이러스가 모두 퍼지면 안전 영역의 크기를 구해야 한다.

     안전 영역의 크기는 

     (Map 전체 크기) - 

             (초기 벽의 개수) - (새로 새운 3개의 벽) - (바이러스로 감염된 방) - (초기 바이러스가 있던 방)

#. Code_v1

직관적으로 바로 풀었을 때,

import java.awt.Point;
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 {
    
    static int N, M, res = 0, map[][], infectedMap[][];
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    static Queue<Point> q;
    static ArrayList<Point> virus;
    
    public static void setupWall(int cnt) {
        // 벽을 세 개 모두 설치했다면
        if(cnt == 3) {
            // 바이러스를 퍼뜨려보자.
            spreadVirus();
            return;
        }
        
        for (int i = 0; i < N*M; i++) {
            // 빈 칸일 경우
            if(map[i/M][i%M] == 0) {
                // 벽을 세워볼까
                map[i/M][i%M] = 1;
                setupWall(cnt+1);
                // 벽을 그냥 안 세울래
                map[i/M][i%M] = 0;
            }
        }
    }
    
    public static void spreadVirus() {
        // 원본 보존을 위해 현재 map을 복사하자.
        infectedMap = new int[N][M];
        for (int i = 0; i < N; i++) 
            System.arraycopy(map[i], 0, infectedMap[i], 0, M);
        
        q = new LinkedList<>();
        // 바이러스의 좌표들을 하나씩 확인하면서
        for (int i = 0; i < virus.size(); i++) {
            Point v = virus.get(i);
            // Queue에 넣어주고
            q.add(new Point(v.x, v.y));
            // 바이러스를 퍼뜨려보자.
            while(!q.isEmpty()) {
                Point now = q.poll();
                
                for (int d = 0; d < 4; d++) {
                    int xx = now.x + dx[d];
                    int yy = now.y + dy[d];
                    // 범위를 벗어나면 pass
                    if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;
                    // 벽이거나 이미 감염된 곳이면 pass
                    if(infectedMap[xx][yy] == 1 ||infectedMap[xx][yy] == 3) continue;
                    // 빈 칸이면 바이러스로 감염시키고 Queue에 add
                    // visited대신 감염된 곳은 3으로
                    infectedMap[xx][yy] = 3;
                    q.add(new Point(xx,yy));
                }
            }
        }
        // 바이러스가 모두 퍼졌을 때, 안전 영역의 크기를 count
        int sum = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < M; y++) {
                if(infectedMap[x][y] == 0) sum += 1;
            }
        }
        
        res = Math.max(res, sum);
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());    // 세로
        M = Integer.parseInt(st.nextToken());    // 가로
        map = new int[N][M];
        virus = 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) virus.add(new Point(i, j));
            }
        }
        
        // 재귀로 3개의 벽을 설치해보자.
        setupWall(0);
 
        System.out.println(res);
    }
}

---

---

#. 연구소 2

#. Problem

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

* The copyright in this matter is in BOJ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ17141 {
    
    static final int max = Integer.MAX_VALUE;
    
    static int N, M, cntSpace, minTime, map[][];
    static List<Point> virusZone;
    static Point[] virus;
    static boolean[][] visited;
    static Queue<Point> q;
    static int[] dr= {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());    // 연구소 크기
        M = Integer.parseInt(st.nextToken());    // 놓을 수 있는 바이러스의 개수
        map = new int[N][N];
        virus = new Point[M];
        virusZone = new ArrayList<>(); // 바이러스를 놓을 수 있는 칸
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 빈 공간일 경우
                if(map[i][j] != 1) cntSpace++;
                // 바이러스를 놓을 수 있는 공간일 경우
                if(map[i][j] == 2) virusZone.add(new Point(i, j));
            }
        }
        
        minTime = max;
        cntSpace -= M; // 바이러스를 놓은 공간은 제외 
        process(0, 0);
        
        // 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우
        if(minTime == max) System.out.println(-1);
        else System.out.println(minTime);
    }
    
    private static void process(int cnt, int start) {
        
        // 모든 바이러스를 설치
        if(cnt == M) {
            int time = spreadVirus();
            minTime = Math.min(minTime, time);
            
            return;
        }
                
        for (int i = start; i < virusZone.size(); i++) {
            // 이 구역에 바이러스를 설치
            virus[cnt] = virusZone.get(i);
            
            process(cnt + 1, i + 1);
        }
    }
 
    private static int spreadVirus() {
        
        int cntSpread = 0, time = -1;
        visited = new boolean[N][N];
        q = new LinkedList<>();
        // 초기 설치된 바이러스의 위치
        for (int i = 0; i < M; i++) {
            q.add(virus[i]);
            visited[virus[i].r][virus[i].c] = true;
        }
 
        // 바이러스 확산
        while(!q.isEmpty()) {
            
            ++time;
            int size = q.size();
            
            while(size-- > 0) {
                Point now = q.poll();
                
                for (int d = 0; d < 4; d++) {
                    int rr = now.r + dr[d];
                    int cc = now.c + dc[d];
                    // 범위를 벗어나면 pass
                    if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;
                    // 벽이거나 이미 방문한 곳이면 pass
                    if(map[rr][cc] == 1 || visited[rr][cc]) continue;
                    // 빈 칸이면 바이러스로 감염시키고 Queue에 add
                    visited[rr][cc] = true;
                    cntSpread++;
                    q.add(new Point(rr,cc));
                }
            }
        }
        
        // 모든 빈 칸에 바이러스가 퍼졌다면
        if(cntSpread == cntSpace) return time;
        return max;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
    }
}