본문 바로가기

알고리즘/알고리즘 문제해결전략

문제 ID : BOARDCOVER , 난이도: 하

반응형
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package test;
 
import java.util.Scanner;
 
public class test{
    public static void main(String[] args) {
        int board[][];
        Scanner scanner = new Scanner(System.in);
        int test = scanner.nextInt();
 
        for(int i = 0; i < test; i++) {
            int y = scanner.nextInt();
            int x = scanner.nextInt();
            board = new int[y][x];
            for(int j = 0; j < y; j++) {
                String str = scanner.next();
                for(int k = 0; k < x; k ++) {
                    board[j][k] = (str.charAt(k) == '#')? 1:0;
                }
            }
String result = "";
            result += (i+1 == test) ? cover(board): cover(board)+"\n";
        }
    }
    static int coverType[][][] = {
            { {00}, {10}, {01} },
            { {00}, {01}, {11} },
            { {00}, {10}, {11} },
            { {00}, {10}, {1-1} }
    };
    
    private static boolean set(int[][] board, int y, int x, int type, int delta) {
        boolean ok = true;
/*
y, x좌표를 기준으로 type에 따라 블럭을 위치시킨다.
아래의 if문 2개로 올바르지 않다면 false를 반환한다.
*/
        for(int i = 0; i < 3; i++) {
            int ny = y + coverType[type][i][0];
            int nx = x + coverType[type][i][1];
           // 위치가 지도를 넘어가지 않는지 검사하는 조건문
if(ny < 0 || ny >= board.length || nx < 0 || nx >= board[0].length)
                ok = false;
/*
좌표에 1을 추가하여 겹치는지 아닌지를 확인해 본다.
delta가 -1일때는 원래 있던 블럭을 치우는 역할을 한다.
*/
            else if((board[ny][nx] += delta) > 1)
                ok = false;
        }
        return ok;
    }
    
    private static int cover(int[][] board) {
        int y = -1, x = -1;
// 비어있는 좌표를 찾는 2중 반복문이다.
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                if(board[i][j] == 0) {
                    y = i;
                    x = j;
                    break;
                }
            }
            if(y != -1)
                break;
        }
//비어있는 공간이 없으면 1을 리턴한다.
        if(y == -1)
            return 1;
        
        int ret = 0;
        for(int type = 0; type < 4; type ++) {
//set 함수를 실행하여 블럭이 정상적으로 채워지면 재귀호출로 다음블럭을 놓는다.
            if(set(board, y, x, type, 1))
                ret += cover(board);
/*
if문에서 조건확인을 위해 set함수를 실행시켰기 때문에 블럭을 올릴 위치에 +1했던값을
다시 -1을 해줌으로서 원래 블럭을 올리기 전의 모습으로 돌아간다.
*/
            set(board, y, x, type, -1);
        }
        return ret;
    }
}
cs

 

반응형