게임판 덮기 (골드2)

2022. 8. 30. 11:49·알고리즘 (with JAVA)/완전 탐색

1. 문제 설명

(1) 게임판 덮기 문제는 아래와 같은 게임판을 이용하여 삼각형( ┌,  ┐, └,  ┘)을 가지고 흰색 칸에 빈틈없이

채울 수 있는 최대 경우의 수를 구하는 것이다.

( 이때, 검은색 칸에는 채울 수 없으며 연속으로 이어져 있다. )

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 문제 입력 수 C를 입력받는다.

 

(2) 두 번째 줄부터는 게임판의 높이 H와 넓이 W를 입력받는다.

( H>=1과 W<=20 )

 

(3) 그 이후 세번째 줄부터는 게임판 크기만큼 흰색과 검은색을 채운다.

( 여기서는 #이 검은색 .이 흰색 )

 

(3) 게임판에 있는 흰칸의 수는 50을 넘지 않아야 한다.

 

(4) 흰 칸에 채워질 도형의 크기는 3칸이므로, 반드시 흰칸의 수는 3배수 이어야 한다.

 

출력 조건

(1) 흰색 칸에 채울 수 있는 최대 경우의 수를 출력한다.

 

입력 예제

 
3
3 7
# . . . . . #
# . . . . . #
# # . . . # #
3 7
# . . . . . #
# . . . . . #
# # . . # # #
8 10
# # # # # # # # # #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# # # # # # # # # #
 

출력 예제

 
0
2
1514
 

 

 

 

3. 풀이 및 코드

: 이 유형의 문제는 항상 특정 순서를 세워서 풀어야 한다.

바로 가장 왼쪽 상단부터 시작하여 삼각형( ┌,  ┐, └,  ┘)을 가지고 하나씩 채우면서 재귀 호출 하는 것이다.

 

또한 삼각형( ┌,  ┐, └,  ┘)은 아래의 표처럼 (0,0) 기준으로 잡고 범위를 체크한다.

  -1 0 1
-1 (-1,-1) (-1,0) (-1,1)
0 (0,-1) (0,0) (0,1)
1 (1,-1) (1,0) (1,1)

또한 삼각형을 넣을때마다 게임판 범위 안에 드는 것인지 흰색과 검은색을 구분하고 삼격형을 넣는 것인지 항상 체크해야

한다.

 

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class BOARDCOVER {
    // 4가지 타입의 시작 블록
    static int[][][] coverType = {
            {{0,0},{1,0},{0,1}}, //┌
            {{0,0},{0,1},{1,1}}, //┐
            {{0,0},{1,0},{1,1}}, //└
            {{0,0},{1,0},{1,-1}} //┘
    };
    
    // 각각 높이, 넓이,흰칸의 수, 게임판, 경우의 수
    static int H,W, wc, ans;
    static int[][] board;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    
    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(sc.readLine());
        
        for(int i=0; i<C; i++) {
            st = new StringTokenizer(sc.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            
            // 흰색 칸의 수와 보드 초기화
            wc=0;
            board = new int[H][W];
            
            // board판에 흰색과 검은색을 채워 넣는 과정
            for(int y=0; y<H; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<W; x++) {
                    String tmp = st.nextToken();
                    
                    // 흰색 칸은 0, 검은색 칸은 1
                    board[y][x] = tmp.equals(".") ? 0:1;
                    
                    if(board[y][x]==0) {
                        wc++;
                    }
                }
            }
            
            // solve()를 호출하는 과정
            // 3의 배수라면 호출
            // 아니면 0 출력
            ans=0;
            if(wc%3==0) {
                solve(wc);
            }
            sb.append(ans+"\n");
        }
        System.out.println(sb);
    }
    
    // 모든 경우의 수를 구해보는 핵심 메서드
    static void solve(int WC) {
        
        
// 기저사례(1): 하나의 경우의 수를 찾은 경우
        if(WC==0) { 
            ans++;
            return;
        }
        
        for(int y=0; y<H; y++) {
            for(int x=0; x<W; x++) {
                if(board[y][x]==0) {
                    for(int k=0; k<4; k++) {
                        if(check(k, y, x)) {
                            set(k, y, x, 1);
                            solve(WC-3);
                            set(k,y,x,0);
                        }
                    }
                    return;
                }
            }
        }
    }
    
    // coverType 4가지가 보드판에 맞는지 확인하는 메서드
    static boolean check(int k, int y, int x) {
        for(int i=0; i<3; i++) {
            int ny = y + coverType[k][i][0];
            int nx = x + coverType[k][i][1];
            
            if(!inRange(ny, nx) || board[ny][nx]==1) {
                return false;
            }
        }
        return true;
    }
    
    // 보드판 범위에 포함하는 지 확인하는 메서드
    static boolean inRange(int ny, int nx) {
        return (ny>=0 && ny<H) && (nx>=0 && nx<W);
    }
    
    // 보드판에 흰색(0) 또는 검은색(1)으로 설정하는 메서드
    static void set(int k, int y, int x, int c) {
        for(int i=0; i<3; i++) {
            int ny = y + coverType[k][i][0];
            int nx = x + coverType[k][i][1];
            board[ny][nx] = c;
        }
    }
}
Colored by Color Scripter
cs
저작자표시 (새창열림)

'알고리즘 (with JAVA) > 완전 탐색' 카테고리의 다른 글

시계 맞추기 (골드1)  (0) 2022.08.31
외판원 문제(TSP, 실버1)  (0) 2022.08.30
소풍 문제  (0) 2022.08.29
보글 게임 (골드2)  (0) 2022.08.29
n개의 원소 중 m개를 고르는 순열과 조합  (0) 2022.08.29
'알고리즘 (with JAVA)/완전 탐색' 카테고리의 다른 글
  • 시계 맞추기 (골드1)
  • 외판원 문제(TSP, 실버1)
  • 소풍 문제
  • 보글 게임 (골드2)
백_곰
백_곰
  • 백_곰
    친절한 코딩
    백_곰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘 (with JAVA)
        • 기본 알고리즘
        • 완전 탐색
        • 분할 정복 알고리즘
        • 동적 계획법
        • 탐욕법
        • 코딩 테스트 기출 문제
        • 코드트리 조별과제
      • 백준 (with JAVA)
        • 완전 탐색
        • 분할 정복
        • 그 외
      • 자바
        • 개발 환경 구축하기
        • 팁
        • 기본적인 개념
        • 컬렉션 프레임워크
        • 프로세스와 쓰레드
        • 지네릭스
        • 람다식
        • 스트림
        • 입출력 IO
        • 네트워킹
        • 열거형(enums)
        • java.lang 패키지
        • java.time 패키지
        • 유용한 클래스들
        • 형식화 클래스들
      • 안드로이드 with 자바
        • 응용 문제들
        • 자잘한 문제들
        • 오류 보고서
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      문자 기반 스트림
      스트림
      map()
      코딩테스트
      선택 정렬
      snail
      ServerSocket
      알고스팟
      InputStream
      Collections Framework
      람다식
      Arrays
      file
      코딩트리조별과제
      다형성
      자바 개념
      유용한 클래스
      불안정 정렬
      소켓 프로그래밍
      안정 정렬
      역직렬화
      안드로이드 스튜디오
      java.time 패키지
      serializable
      java.lang패키지
      outputstream
      중간연산
      TCP 소켓 프로그래밍
      제자리 정렬
      코드트리
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    백_곰
    게임판 덮기 (골드2)
    상단으로

    티스토리툴바