코드트리 <격자 칠하기 2>

격자 칠하기 2

---

문제 해결

숫자들의 차이인 D를 이진탐색을 활용해 찾았다.

 

binarySearch 함수

• start는 0이고, end는 1000000으로 설정했다. 왜냐면 칸에 적힌 숫자가 0과 1000000 사이이기 때문이다.
• mid를 D라고 생각했을 때,
• 만약 색칠된 칸이 전체 칸의 반 이상이라면
  • 먼저 Answer을 갱신해주고, 덜 색칠하기 위해 D의 값을 줄여야 한다. 즉, end의 값을 mid-1로 업데이트한다.
• 만약 색칠된 칸이 전체 칸의 반보다 적다면
  • 더 색칠하기 위해 D의 값을 키워야 한다. 즉, start의 값을 mid+1로 업데이트한다.
• 이때 색칠된 칸이 전체 칸의 반 이상인 것을 알기 위해 isColored 함수를 사용한다. 

isColored(int d) 함수

• (0, 0) 부터 (N-1, N-1) 까지 돌면서 방문하지 않은 곳이라면 coloring 함수를 불러서 해당 칸을 시작으로 색칠한 칸의 개수를 구한다. 
• coloring 함수를 불러서 구한 색칠 칸의 개수가 가장 큰 값을 기준으로 전체 칸의 반 이상인지 확인한다. (그렇기 때문에 visit 배열은 공유하여 사용한다.)
• 만약 반 이상이라면 true를 반환하고 그렇지 않다면 false를 반환한다.

coloring(int i, int j, int d, boolean[][] visit) 함수

• BFS를 활용하여 차이가 d 이하인 인접한 곳을 방문해나가며 색칠한 칸의 개수를 구한다.
• 시작 지점을 큐에 넣고 큐가 빌 때까지 다음 로직을 수행한다.
• 큐에서 원소를 하나(poll) 꺼낸다.
• 이 원소를 기준으로 인접한 곳을 방문하는데
  • 범위를 벗어나거나, 이미 방문했거나, 기준 지점과 인접 지점의 숫자 차이가 d보다 크다면 방문하지 않는다.
  • 위의 경우가 아니라면 큐에 인접 지점을 넣고, 방문 체크를 진행한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    static int N, Answer;
    static int[][] Number;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        Number = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] inArr = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                Number[i][j] = Integer.parseInt(inArr[j]);
            }
        }
        // end input

        Answer = Integer.MAX_VALUE;
        binarySearch();
        System.out.println(Answer);

    }
    static void binarySearch() {
        int start = 0;
        int end = 1000000;
        while (start <= end) {
            int mid = (start + end) / 2;
            // 색칠된 칸이 전체 칸의 반 이상이라면 -> 좀 덜 색칠해보자
            if (isColored(mid)) {
                end = mid - 1;
                Answer = Math.min(Answer, mid);
            } else { // 그렇지 않다면 -> 더 많이 색칠해야 됨
                start = mid + 1;
            }
        }
    }

    private static boolean isColored(int d) {
        int count = 0;
        boolean[][] visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j]) continue;
                count = Math.max(coloring(i, j, d, visit), count);
            }
        }
        // 반올림해서 하기 때문에 +1 한 다음에 2로 나누기
        int half = (N * N + 1) / 2;
        // 방문한 곳이 half개 이상이면 true
        if (count >= half) return true;
        return false;
    }

    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    private static int coloring(int i, int j, int d, boolean[][] visit) {
        Queue<int[]> Q = new ArrayDeque<>();
        Q.add(new int[]{i, j});
        visit[i][j] = true;
        int cnt = 1;
        while (!Q.isEmpty()) {
            int[] poll = Q.poll();
            for (int k = 0; k < 4; k++) {
                int ni = poll[0] + di[k];
                int nj = poll[1] + dj[k];
                // 범위를 벗어났거나 방문했으면 안됨
                if (ni < 0 || nj < 0 || ni >= N || nj >= N || visit[ni][nj]) continue;
                // 인접한 곳과 차이가 d 이상이면 안됨
                if ( Math.abs(Number[poll[0]][poll[1]] - Number[ni][nj]) > d) continue;
                // 새로운 곳 방문
                Q.add(new int[]{ni, nj});
                visit[ni][nj] = true;
                cnt++;
            }
        }
        return cnt;
    }
}

---

출처

https://www.codetree.ai/missions/8/problems/painting-the-grid-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---