SWEA 14413. 격자판 칠하기

검은색과 흰색, 빈 공간으로 채워져있는 격자판을 마주한 칸 끼리 색이 다르게 할 수 있는지 확인하는 문제이다. 빈 공간은 검은색, 흰색 둘 중 하나로 칠할 수 있다.

 

빈 공간이 아닌 칸들 부터 좌표를 기준으로 주변을 퍼져나가면서 빈 공간이면 현재 색과 다른 색을 칠하고 빈 공간이 아니면 현재 칸과 주변 칸이 같으면 불가능하게 된다. 끝까지 칠할 수 있게 되면 마주한 칸 끼리 색이 다르게 칠할 수 있다는 의미이다. BFS로 주변을 탐색하였다.

char[][] board = new char[n][m];
Deque<int[]> queue = new ArrayDeque<>();
for(int i=0; i<n; i++) {
    String line = br.readLine();
    board[i] = line.toCharArray();
    for(int j=0; j<m; j++) {
        if(board[i][j] != '?') {
            queue.add(new int[] {i, j});
        }
    }
}
            
while(!queue.isEmpty()) {
    int[] current = queue.remove();
    char next = board[current[0]][current[1]] == '.' ? '#' : '.';
    for(int i=0; i<4; i++) {
        int nr = current[0] + dr[i], nc = current[1] + dc[i];
        if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
        if(board[nr][nc] == board[current[0]][current[1]]) {
            sb.append("impossible").append('\n');
            continue outer;
        }
        if(board[nr][nc] != '?') continue;
        board[nr][nc] = next;
        queue.add(new int[] {nr, nc});
    }
}
sb.append("possible").append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] dr = {0, 0, -1, 1};
        int[] dc = {-1, 1, 0, 0};

        outer: for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
            char[][] board = new char[n][m];
            Deque<int[]> queue = new ArrayDeque<>();
            for(int i=0; i<n; i++) {
                String line = br.readLine();
                board[i] = line.toCharArray();
                for(int j=0; j<m; j++) {
                    if(board[i][j] != '?') {
                        queue.add(new int[] {i, j});
                    }
                }
            }
            
            while(!queue.isEmpty()) {
                int[] current = queue.remove();
                char next = board[current[0]][current[1]] == '.' ? '#' : '.';
                for(int i=0; i<4; i++) {
                    int nr = current[0] + dr[i], nc = current[1] + dc[i];
                    if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if(board[nr][nc] == board[current[0]][current[1]]) {
                        sb.append("impossible").append('\n');
                        continue outer;
                    }
                    if(board[nr][nc] != '?') continue;
                    board[nr][nc] = next;
                    queue.add(new int[] {nr, nc});
                }
            }
            sb.append("possible").append('\n');
            
        }
        
        br.close();
        System.out.print(sb);
    }
}