[BOJ] #14502 연구소, #18405 경쟁적 전염, #2630 색종이 (JAVA)

#14502 연구소

문제이해

0, 1, 2 숫자가 있고 벽(1)을 3개 추가로 세워서 바이러스(2)가 퍼지는 수를 막아서 최대한 빈칸(0)의 개수가 큰 걸 찾아야 한다. 

 

 

해결 방법 고안

- 벽을 3개 세우고 -> 바이러스 퍼지고 -> 0개수 세기

- 위에 로직을 계속 반복해야 하는 구조이다.

- 그래서 벽을 세우는 건 dfs, 바이러스 퍼지는건 bfs, 개수 세는 함수 이렇게 총 3개의 함수를 만들기로 하였다.

- 최종으로 최대한 큰 max_value를 찾아서 결과를 출력해주면 끝이다.

코드설명

아래 코드에 주석으로 달아놓았다.

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

public class Main {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuffer output = new StringBuffer();
    private static StringTokenizer tokens;
    private static int n,m;
    private static int[][] map;
    private static int[][] temp;
    private static boolean [][] visited;
    private static int [][] deltas = {{0,1}, {1,0}, {-1,0},{0,-1}};
    private static int max_value = Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            tokens = new StringTokenizer(input.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }
        dfs(0);
        System.out.println(max_value);
    }
	//벽을 3개 세우는 함수
    private static void dfs(int count) { 
        if (count == 3) {
            virus();
            int total = sum(temp); //현재의 개수
            max_value = Math.max(total, max_value);
            //1. 바이러스 퍼뜨림
            //2. 그 당시 temp의 개수셈
            //3. 큰 것을 고름
            return;
        }
        //벽 3개가 차지 않았을 때 벽을 3개 세우는거
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1; //벽을 세우는거
                    dfs(count+1); //3개 될때까지 호출
                    map[i][j]=0; //다시 백
                }
            }
        }
    }
    //바이러스 퍼지는 함수
    private static void virus () {
        
        // 원래 map은 바이러스에 영향을 받지 않으므로 복사함
        temp = new int[n][m];
        for (int i = 0; i < n; i++) {
            temp[i] = map[i].clone();
        }
        visited = new boolean[n][m]; //초기화
        //맨 처음의 바이러스를 큐에 넣어야 한다
        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (temp[i][j] == 2) {
                    que.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        while (!que.isEmpty()) {
            int t[] = que.poll();
            int dx = t[0];
            int dy = t[1];
            for (int d[] : deltas) {
                int nx = dx + d[0];
                int ny = dy + d[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && temp[nx][ny] == 0) {
                    if (!visited[nx][ny]) {
                        temp[nx][ny] = 2;
                        que.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
    //0의 개수 세는 함수
    private static int sum ( int[][] temp){
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (temp[i][j] == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}

 

여기서의 포인트는 bfs, dfs를 동시에 사용해야한다는 것

temp 배열을 이용해 virus함수에서 복사를 해서 퍼져야하는 것 (원래 배열은 벽을 세우는 용도로만)

바이러스를 퍼뜨리고 다시 visited를 초기화 해야한다는 것

이렇게 총 3가지인듯 하다.

 

#18405 경쟁적 전염

문제 이해

초기에 있던 바이러스의 숫자대로 시간이 1초 지나면 바이러스가 퍼져야 한다.

주의할 점은 1. 오름차순 순서대로 바이러스가 퍼지는 것 2. 주어진 시간이 되면 바이러스가 끝나는 것

 

해결 방법 고안

- 상하좌우로 퍼져야 하기에 bfs를 생각했다

- que에 count를 넣어서 s와 크거나 같을 때 반복을 중단한다고 조건을 걸었다

- 작은 순서대로 퍼져야 하기 때문에 초기에 위치를 넣고 que를 정렬해야 한다.

- que 정렬은list를 만들고 que에 list를 넣고 Comparator를 사용해서 정렬하고 list를 다시 que로 바꾸어 주었다.

 

코드 설명

package chapter13;
import java.util.*;
import java.io.*;

public class Boj18405 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    static int deltas[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {

        tokens = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(tokens.nextToken());
        int k = Integer.parseInt(tokens.nextToken());
        int map[][] = new int[n][n];
        Queue<int[]> que = new LinkedList<>();

        // Reading the map and initializing the queue with the virus positions
        for (int i = 0; i < n; i++) {
            tokens = new StringTokenizer(input.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                if (map[i][j] != 0) {
                    que.offer(new int[]{map[i][j], i, j, 0});
                }
            }
        }

        tokens = new StringTokenizer(input.readLine());
        int s = Integer.parseInt(tokens.nextToken());
        int x = Integer.parseInt(tokens.nextToken());
        int y = Integer.parseInt(tokens.nextToken());

        List <int[]> list = new ArrayList<>(que);
        list.sort(Comparator.comparingInt(a->a[0]));
        que = new LinkedList<>(list);
        while (!que.isEmpty()) {
            int t[] = que.poll();
            int v = t[0];
            int dx = t[1];
            int dy = t[2];
            int count = t[3];

            if(count >= s) {
                break;
            }

            for (int[] d : deltas) {
                int nx = dx + d[0];
                int ny = dy + d[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (map[nx][ny] == 0) {
                        map[nx][ny] = v;
                        que.offer(new int[]{v, nx, ny, count + 1});
                    }
                }
            }
        }

        System.out.println(map[x-1][y-1]);
    }
}

 

이번 기회에 Compator을 다시 구현해보았당

#2630 색종이

문제설명

재귀 문제이다. 색종이를 같은 색이 있을 때까지 나눈다.

종료 조건은 정사각형의 모양이 다 같은 색일 때까지이다. (크기가 1일 때도 하나임으로 같은 색으로 처리한다.)

 

코드 설명

public class Main {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static int n;
    private static int[][] map;
    private static int white, blue;
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(input.readLine());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            tokens = new StringTokenizer(input.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }
        divide(0,0,n);
        System.out.println(white);
        System.out.println(blue);
    }
    private static void divide(int r, int c, int len) {
        if(check(r, c, len)){
            if(map[r][c] == 0){
                white++;
            }
            else {
                blue++;
            }
            return;
        }
        int divide_len = len/2;
        divide(r,c,divide_len);
        divide(r,c+divide_len,divide_len);
        divide(r+divide_len,c,divide_len);
        divide(r+divide_len,c+divide_len,divide_len);
    }
    //같은 색인지 확인
    private static boolean check(int r, int c, int len) {
        int current = map[r][c];
        for (int i = r; i < r+len; i++) {
            for (int j = c; j < c+len; j++) {
                if (map[i][j] != current) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

같은 색인지 확인하는 함수 하나, 나눌 수 있을 때까지 나누는 함수 하나(재귀)

이렇게 구현했다!