[문제][알고스팟] BOARDCOVER (게임판 덮기)

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOARDCOVER
  • 2000ms
  • 65536kb
  • 5938
  • 2724 (45%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, .는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

예제 입력

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

예제 출력

0
2
1514

---

며칠전에 풀었지만 이제 포스팅한다.

여전히 문제는 풀기싫다. 하지만 마무리 하면 뿌듯하다. 마치 수영처럼.

정답 풀이 접근법과 내가 최초로 접근한 방식은 거의 유사했다.

1) 하지만 채워야하는 도형의 모양을 더 단순화 시킬 수 있었는데, 그 부분을 놓쳤다.

어차피 왼쪽 위는 모두 채워져 있다고 가정해야 채워지는 가짓수를 중복해서 세지 않을 수 있기 때문에, 왼쪽이나 위를 침범하는 도형의 모양은 고려하지 않아도 된다.

따라서 아래 소스의 coverType과 같이 4가지 유형의 도형만 고려하면 된다.

2) 도형을 덮었다가 다시 원복할때 delta 파라미터로 -1 또는 1값을 주어서 해결하는 방법도 생각하지 못했다. 이런건 킵해야한다.

나머지는 유사하다. 

아래는 정답 코드이다.

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BoardcoverSolution {
	
	public static int W,H;
	public 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} },
			};
	public static int board[][];
	public static int count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("D://sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		
		for(int tc=1; tc<=T; tc++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			H = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			
			board = new int[H][W];
			
			for(int i=0; i<H; i++){
				String row = br.readLine().trim();
				for(int j=0; j<W; j++){
					int ch = row.charAt(j);
					if('#' == ch){
						board[i][j] = 1;
					}else{
						board[i][j] = 0;
					}
				}
				
			}
			
			count = cover();
			
			bw.flush();
			bw.write(count + "\n");
			
		}
		
		bw.close();

	}
	
	// board의 (y,x)를 type번 방법으로 덮거나, 덮었언 블록을 없앤다.
	// delta = 1 이면 덮고, -1이면 덮었던 블록을 없앤다.
	// 만약 블록이 제대로 덮이지 않은 경우 (게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때) false 반환한다.
	public static boolean set(int y, int x, int type, int delta) {
		boolean ok = true;
		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 >= H || nx < 0 || nx >= W) {
				ok = false;
			}else if((board[ny][nx] += delta) > 1) {
				ok = false;
			}
		}
		
		return ok;
	}
	
	// board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
	// board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
	// board[i][j] = 0 아직 덮이지 않은 칸
	public static int cover() {
		// 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
		int y = -1, x = -1;
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; 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++) {
			// 만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출한다.
			if(set(y,x,type,1)) {
				ret += cover();
			}
			// 덮었던 블록을 치운다.
			set(y,x,type,-1);
		}
		
		return ret;
		
	}
	

}