[백준] 1553 - 도미노 by C++

https://www.acmicpc.net/problem/1553

1553번: 도미노 찾기

진짜 금방 풀 수 있었는데,

배열 접근 범위 제한과정에서 실수를 했다.

평상 시에 거의 하지 않는 실수여서 찾는데 너무 오래걸렸다 ㅠㅠ

침착하게 차근차근 코드를 짜자

 

핵심 변수

int board[8][7] : 입력된 격자를 저장

int vis[8][7] : 격자가 도미노로 채워졌는지 여부를 확인

int domino[7][7] : (r, c)의 값을 가지는 도미노의 잔여 여부 확인

void func(int r, int c, int usedDomino) : 재귀함수, 새로 탐색할 위치(r, c)와 지금까지 사용된 도미노의 개수를 입력

answer : 결과값

 

알고리즘 방식

재귀를 사용한 백트래킹 문제였다.

1. 아래와 같이 (0, 0)에서 시작하여 가로 2칸, 세로 2칸을 각각 남아있는 도미노로 채울 수 있는지 확인

2. 만약 채울 수 있다면,

    2-1. domino배열에서 사용된 도미노를 제거

    2-2. vis배열에서 도미노가 채워진 위치를 1로 변경 (2칸 모두)

    2-3. 만약 지금까지 사용된 도미노가 28개(전체)라면 answer++ 및 아래 2-4과정 생략

    2-4. func에 새로운 위치와 지금까지 사용된 도미노의 개수를 입력하여 호출

           여기서 새로운 위치는 현재 위치를 기준으로 column쪽으로 진행하며 vis값이 0인 위치

           만약 column이 끝까지 진행됐을 경우, 다음 row의 column = 0 부터 다시 vis값이 0인 위치 탐색

           (이 선택과정을 다르게할 경우,

            1. 에서의 2개가 아닌, 최대 위쪽 | 왼쪽으로의 도미노 존재 여부까지 확인해주어야함)

3. 2-4의 func이 반환되었을 경우, 모든 경우를 탐색해야하므로 2-1, 2-2과정을 취소

    (domino배열에 사용된 도미노 추가 및 vis배열에서 도미노가 채워졌던 위치를 0로 변경)

 

 

소스코드

#include <iostream>
 
using namespace std;
 
char bufBoard[8][7];
int board[8][7];
char vis[8][7];
int domino[7][7];
int answer;
int dx[2] = { 0, 1 };
int dy[2] = { 1, 0 };
 
void func(int r, int c, int usedDomino) {
	for (int dir = 0; dir < 2; dir++) {
		int nx = r + dx[dir];
		int ny = c + dy[dir];
 
		if (nx < 0 || ny < 0 || nx >= 8 || ny >= 7)
			continue;
 
		pair<int, int> dominoNum;
		if (board[r][c] > board[nx][ny])
			dominoNum = { board[nx][ny], board[r][c] };
		else
			dominoNum = { board[r][c], board[nx][ny] };
 
		if (domino[dominoNum.first][dominoNum.second] == 1 && vis[nx][ny] == 0) {
			domino[dominoNum.first][dominoNum.second] = 0;
			vis[r][c] = 1;
			vis[nx][ny] = 1;
 
			for (int i = r * 7 + c + 1; i < r * 7 + c + 14; i++) {
				if (i >= 56)
					break;
 
				if (usedDomino == 27) {
					answer++;
					break;
				}
 
				if (vis[i / 7][i % 7] == 0) {
					//cout << dominoNum.first << ' ' << dominoNum.second << ' ' << usedDomino + 1 << '\n';
					func(i / 7, i % 7, usedDomino + 1);
					break;
				}
			}
			domino[dominoNum.first][dominoNum.second] = 1;
			vis[r][c] = 0;
			vis[nx][ny] = 0;
		}
	}
	return;
}
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	for (int i = 0; i < 8; i++) 
		cin >> bufBoard[i];
 
	for (int i = 0; i < 8; i++) 
		for (int j = 0; j < 7; j++) 
			board[i][j] = bufBoard[i][j] - '0';
 
	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7; j++) {
			if (i > j)
				continue;
			domino[i][j] = 1;
		}
	}
 
	func(0, 0, 0);
 
	cout << answer;
}