[G4] 백준 14500번 테트로미노 C++ 구현, 백트래킹

리뷰

 

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

각 위치마다 일반적인 4방향 백트래킹을 돌린다. ㅗ모양은 방향배열로 알 수 없어 해당 부분만 추가로 체크해 준다.

ㅓㅗㅜㅏ 네개만 체크했다가 한번 틀렸다, 체크해야할 모양은 총 8개이다.

 

 

전역 변수

• n, m : 맵의 세로 길이 n, 맵의 가로 길이 m
• ans : 정답을 저장하고 출력하기 위한 변수
• dx, dy : 8방향 탐색을 위한 방향 배열
• lst : 맵 정보를 저장하기 위한 정수형 2차 배열
• v : 방문 표시를 해주기 위한 정수형 2차 배열
• h : ㅗ모양을 했을때 각 모양의 값을 저장하기 위한 정수형 배열

 

함수

1. input

void input()

 

n, m을 입력 받고 맵 정보인 lst배열을 입력받기 위한 함수

 

2. bt

void bt(int level, int sx, int sy, int sum)

 

백트래킹을 통해 ㅗ모양을 제외한 나머지 모양의 값의 합을 구하는 함수

1. 매개변수로 재귀 단계 level, 현재 좌표 sx, sy, 여태까지의 합 sum을 입력받는다.
2. 기저조건은 level이 4에 도달했을 때이며, ans와 sum을 비교하여 더 큰값을 ans로 저장하고 리턴한다.
3. 4방향 탐색을 하고 맵 범위 내에 있으며 방문하지 않은 곳이라면 이동을 진행한다.
4. 방문 표시 후 level + 1, 이동한 위치 좌표, sum + 이동한 위치의 값으로 재귀를 진행한다.
5. 재귀를 빠져나오며 방문 표시 했던 내용을 지워준다.

3. chk

void chk(int sx, int sy)

 

ㅗ모양을 탐색해 주기 위한 함수

1. 현재 위치의 좌표 sx, sy를 매개변수로 받는다.
2. 현재위치 기준 ㅜㅏㅗㅓ의 값을 구해 각각 h의 0~3인덱스에 저장해 준다.
3. 현재 위치 기준 ㅗㅓㅜㅏ의 값을 구해 각각 h의 4~7 인덱스에 저장해 준다.
4. ans를 h배열의 최대값과 비교하여 더 큰 값을 ans에 저장해 준다.

4. solution

void solution()

 

전 맵을 돌며 모든 케이스를 확인하기 위한 브루트포스 함수

1. n * m맵을 순회하며 모든 좌표에서 백트래킹을 수행해 준다.
2. 수행 전 방문표시 후 1, i, j, lst[i][j]를 백트래킹의 초기 매개변수로 전달해 준다.
3. 백트래킹 완료 시 방문처리를 해제해 준다.
4. 만약 i, j가 1, 1 ~ n - 2, m - 2범위 내에 있다면 chk 함수를 실행해 준다.

 

문제풀이

1. input함수를 실행하여 각 변수와 배열에 값을 입력 받는다.
2. solution함수를 실행하여 맵의 모든 범위에서의 최대값을 ans변수에 저장해 준다.
3. ans변수에 저장된 값을 출력해 준다.

 

참고 사항

chk함수는 맵의 가장자리에서 실행하면 IndexError가 출력된다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, ans;
int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, -1, 1 };
int lst[500][500];
int v[500][500];
int h[8];

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
		}
	}
}

void bt(int level, int sx, int sy, int sum) {
	if (level == 4) {
		ans = max(ans, sum);
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int nx = sx + dx[i], ny = sy + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
			v[nx][ny] = 1;
			bt(level + 1, nx, ny, sum + lst[nx][ny]);
			v[nx][ny] = 0;
		}
	}
}

void chk(int sx, int sy) {
	h[0] = lst[sx][sy] + lst[sx - 1][sy - 1] + lst[sx - 1][sy] + lst[sx - 1][sy + 1];
	h[1] = lst[sx][sy] + lst[sx - 1][sy - 1] + lst[sx][sy - 1] + lst[sx + 1][sy - 1];
	h[2] = lst[sx][sy] + lst[sx + 1][sy - 1] + lst[sx + 1][sy] + lst[sx + 1][sy + 1];
	h[3] = lst[sx][sy] + lst[sx - 1][sy + 1] + lst[sx][sy + 1] + lst[sx + 1][sy + 1];
	h[4] = lst[sx][sy] + lst[sx][sy - 1] + lst[sx - 1][sy] + lst[sx][sy + 1];
	h[5] = lst[sx][sy] + lst[sx][sy - 1] + lst[sx - 1][sy] + lst[sx + 1][sy];
	h[6] = lst[sx][sy] + lst[sx][sy - 1] + lst[sx + 1][sy] + lst[sx][sy + 1];
	h[7] = lst[sx][sy] + lst[sx][sy + 1] + lst[sx - 1][sy] + lst[sx + 1][sy];
	ans = max(ans, *max_element(h, h + 8));
}

void solution() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			v[i][j] = 1;
			bt(1, i, j, lst[i][j]);
			v[i][j] = 0;
			if (i >= 1 && j >= 1 && i < n - 1 && j < m - 1) chk(i, j);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	solution();	
	cout << ans;
}