[SW expert Academy] SWEA 14413번 격자판 칠하기 자바(Java)

[D3] 격자판 칠하기 - 14413

문제 링크

성능 요약

메모리: 36,684 KB, 시간: 181 ms, 코드길이: 2,264 Bytes

제출 일자

2023-10-22 20:00

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

 

생각 했던 풀이
1. for문을 돌려서 현재 위치 인덱스의 값이 '?'가 아니라면 BFS 함수를 통해서 격차를 채워준다.
2. 만약 채우는 도중 배열의 cur값과 next값이 같으면 invalid한 값이므로 return false
3. false를 리턴하지 않는다면 valid한 값

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		char[][] map;
        
        int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            String result = "possible";
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            map = new char[a][b];
            for(int i = 0; i < a; i++){
                String line = sc.next();
                for(int j = 0; j < b; j++){
                    map[i][j] = line.charAt(j);
                }
            }

            loop : for(int i = 0; i < a; i++){
                for(int j = 0; j < b; j++){
                    if(map[i][j] != '?'){
                        if(!solution(map,i,j)){
                            result = "impossible";
                            break loop;
                        }
                    }
                }
            }
            
            System.out.printf("#%d %s\n",tc,result);
        }
	}
    
    private static boolean solution(char[][] map, int x, int y){
        int[] dirX = {1,-1,0,0};
        int[] dirY = {0,0,-1,1};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];
            
            for(int i =0; i < 4; i++){
                int nextX = curX + dirX[i];
                int nextY = curY + dirY[i];
                
                // 범위보다 크거나 이미 문자가 존재할 때
                if((nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length)){
                    continue;
                }

                if(map[nextX][nextY] == map[curX][curY]){
                    return false;
                }
                
                if(map[nextX][nextY] != '?'){
                    continue;
                }

                if(map[curX][curY] == '#'){
                    map[nextX][nextY] = '.';
                }else{
                    map[nextX][nextY] = '#';
                }
                queue.offer(new int[]{nextX,nextY});
            }
        }
       	return true;
    }
}

더 쉬운 풀이
1. 격자판의 성질을 이용한다. 
2. 두가지 경우의 수를 놓고 생각한다. 0,2,4....등의 짝수번째 위치와 1,3,5...등 홀수번째 위치가 같지 않다면 가능함
3. 홀수번째 인덱스의 value 짝수번째 인덱스의 value가 같다면? invalid한 경우임

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		char[][] map;
        
        int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            String result = "impossible";
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            map = new char[a][b];
            for(int i = 0; i < a; i++){
                String line = sc.next();
                for(int j = 0; j < b; j++){
                    map[i][j] = line.charAt(j);
                }
            }
			if(check(map,'#','.') || check(map,'.','#')) {
                result = "possible";
            }
            
            System.out.printf("#%d %s\n",tc,result);
        }
	}
    
	private static boolean check(char[][] map,char a,char b){
        for(int i =0; i < map.length; i++){
            for(int j = 0; j < map[0].length; j++){
                if((i + j) % 2 == 0 && map[i][j] == a){
                    return false;
                }else if((i + j) % 2 == 1 && map[i][j] == b){
                    return false;
                }
            }
        }
        return true;
    }
}

처음부터 너무 어렵게 생각하지말기