[코드트리] 격자 칠하기 2 - Java

📝 문제

문제 | [코드트리] 격자 칠하기 2

💡 풀이 과정

⛓ 사용한 알고리즘 : 이분탐색, BFS

아이디어

풀이를 크게 두 파트로 나누면 다음과 같다.

1. D의 값 탐색하기
2. 1번에서 탐색한 D의 값으로 칠할 수 있는 칸의 수 세기

위 과정을 수행한 뒤, 선택한 D의 값으로 칠할 수 있는 칸의 수가 전체 격자의 과반수 이상인지를 판별해주어 최솟값을 찾아가면 된다.

1번 파트 - 이분탐색

우선 D의 값의 최솟값은 0, 최댓값은 1,000,000이다(격자에 적힌 숫자의 범위). 따라서 효율적으로 D의 값을 탐색하기 위해 이분탐색을 활용하였다. 만약 선택한 D의 값으로 과반수 이상의 격자를 칠할 수 있다면 최솟값을 찾아야 하므로 r 을 mid-1 로 설정한다. 반대의 경우에는 l 을 mid+1 로 설정하여 가능한 D값을 다시 탐색한다.

2번 파트 - BFS

D값을 선택했다면 BFS를 이용하여 현재 D값으로 한 번에 칠할 수 있는 격자의 최대 개수를 구한다. 이 때 색칠하는 시작점이 정해져있지 않으므로, 방문하지 않은 모든 격자에서 BFS를 수행한다. 쉽게 말해 격자 안에서 이동이 가능한 칸들의 덩어리를 찾고, 그 덩어리의 최댓값을 탐색한다.

BFS를 모든 칸에서 수행한 후 찾아낸 최댓값이 전체 격자의 과반수이지 판별한다. 만약 과반수를 넘는다면 앞서 선택한 D값이 유효한 값이므로 이를 갱신해주고, 그렇지 않은 경우에는 다시 1번 파트로 돌아가 D값을 탐색한다.

코드

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

public class Main {

    static int N;

    static int[][] map;
    static boolean[][] visit;

    static int[] di = {-1,1,0,0};
    static int[] dj = {0,0,-1,1};

    static int coloring(int si, int sj, int D) {
        Queue<int[]> q = new LinkedList<>();
        
        q.offer(new int[] {si, sj});
        visit[si][sj] = true;

        int cnt=1;
        while(!q.isEmpty()) {
            int ti = q.peek()[0];
            int tj = q.poll()[1];

            for(int d=0;d<4;d++) {
                int ni = ti+di[d];
                int nj = tj+dj[d];

                if(ni<0 || ni>=N || nj<0 || nj>=N) continue;
                if(visit[ni][nj]) continue;
                if(Math.abs(map[ti][tj]-map[ni][nj])>D) continue; 

                q.offer(new int[] {ni,nj});
                visit[ni][nj] = true;
                cnt++;
            }
        }

        return cnt;
    }

    static boolean isHalf(int D) {
        visit = new boolean[N][N];
        int cnt = 0;
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(visit[i][j]) continue;
                int tmp = coloring(i, j, D);
                cnt = Math.max(cnt, tmp);
            }
        }

        if(cnt>=(N*N+1)/2) 
            return true;
        
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        StringTokenizer st;
        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());
            }
        } //end input

        int l=0,r=1_000_000;
        int ans = Integer.MAX_VALUE;
        while(l<=r) {
            int mid = (l+r)/2;
            if(isHalf(mid)) {
                r = mid-1;
                ans = Math.min(ans, mid);
            } else {
                l = mid+1;
            }
        }

        System.out.println(ans);
    }
}