[비트마스킹][완전 탐색] 14391 종이 조각 c++구현

목차

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

문제

 

 

문제 풀이 시 아이디어

1. 종이 자르기

이 문제는 종이 자르는 것을 코드로 구현하는 것이 매우 까다로워 아이디어가 필요한 문제였다.

0: 가로 1: 세로 라고 방향을 정해놓고 비트마스킹을 통해 모든 0과 1의 조합을 구해서 탐색하면 된다.

1	0	0	1
0	0	1	1
1	1	0	0
0	0	1	0

 

이렇게 방향을 정하면 자르는 것이 매우 수월하다.

 

2. 인덱스 구하기: %연산자와 /연산자를 통해 

아래와 같이 수 하나를 이차원 배열의 인덱스로 나눌 수 있다.

그 이후 비트마스킹을 통해 모든 경우를 구하자

	for (int i = 0; i < (1 << N * M); i++) {
		for (int j = 0; j < N * M; j++) {
			if (i & (1 << j)) {
				direct[j / M][j % M] = 1;
			}
		}
		maxNum = max(maxNum, Search());
		fill(&direct[0][0], &direct[0][0] + 6 * 6, 0);
		fill(&visit[0][0], &visit[0][0] + 6 * 6, 0);
		
	}

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

int N, M;

int board[8][8] = { 0 };
int direct[8][8] = { 0 };
// 아이디어 -> 0: 가로  1: 세로
int visit[8][8] = { 0 };
int maxNum = 0;


int Search() {
	int total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			string num;
			if (!visit[i][j]) {
				int first = direct[i][j];  //처음 방향
				visit[i][j] = 1;  //방문 처리
				num += board[i][j] +'0';
				if (first) {  //세로 방향
					int x = j;
					int y = i;
					while (1) {
						y++;
						if (y > N-1)
							break;
						if (!direct[y][x])
							break;
						if (visit[y][x])
							break;
						visit[y][x] = 1;
						num += board[y][x] +'0';
					}

					total += atoi(num.c_str());  //누적
				}
				else {   //가로 방향
					int x = j;
					int y = i;
					while (1) {
						x++;
						if (x > M-1)
							break;
						if (direct[y][x])
							break;
						if (visit[y][x])
							break;
						visit[y][x] = 1;
						num += board[y][x] +'0';
					}

					total += atoi(num.c_str());  //누적
				}
			}
	
		}
	}
	return total;
}

int main() {
	int num;
	string str;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int j = 0; j < M; j++) {
			board[i][j] = str[j]-'0';
		}
	}
	for (int i = 0; i < (1 << N * M); i++) {
		for (int j = 0; j < N * M; j++) {
			if (i & (1 << j)) {
				direct[j / M][j % M] = 1;
			}
		}

		maxNum = max(maxNum, Search());
		fill(&direct[0][0], &direct[0][0] + 6 * 6, 0);
		fill(&visit[0][0], &visit[0][0] + 6 * 6, 0);
		
	}
	cout << maxNum;

}