SW Expert 12052 JAVA : 부서진 타일

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AXmwOSJaSNIDFARX&categoryId=AXmwOSJaSNIDFARX&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=4

SW Expert Academy

 

풀이 예상

타일이 무조건 2x2 이기 때문에 탐색을 하면서 만나는 부서진 타일을 정사각형의 왼쪽 위를 기준으로 두고, 오른쪽, 오른쪽아래 대각선, 아래를 확인하면서 범위가 넘었거나 부서지지 않은 타일이라면 NO를 반환한다.

탐색부분	확인
확인	확인

 

이때 부서진 타일은 부서지지 않은 타일로 바꾼다.

모든 타일을 탐색하고 NO를 반환하지 않았다면 YES를 반환한다.

 

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N^2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, M;
    static boolean[][] tile;
    static int[] dr = {0, 1, 1};
    static int[] dc = {1, 1, 0};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T ; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            tile = new boolean[N][M];
 
            for (int i = 0; i < N; i++) {
                String str = br.readLine();
                for (int j = 0; j < M; j++) {
                    char c = str.charAt(j);
                    if(c == '.') {
                        tile[i][j] = true; //부서진타일: false, 안깨진타일: true
                    }
                }
            }
 
            sb.append("#").append(t).append(" ");
            sb.append(checkTile());
            sb.append("\n");
        }
        System.out.println(sb);
 
    }
    static boolean check (int nr, int nc) {
        return nr>=0 && nr<N && nc>=0 && nc<M;
    }
    static String checkTile() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(!tile[i][j]) {
                    //부서진 타일이라면 오른쪽, 오른쪽대각선아래, 아래 위치를 확인
                    for (int d = 0; d < 3; d++) {
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if(!check(nr,nc)) {
                            return "NO";
                        }
                        if(tile[nr][nc]) {
                            return "NO";
                        }else {
                            tile[nr][nc] = true;
                        }
                    }
                }
 
            }
        }
        return "YES";
    }
}

 

결과