6. [백준 14500번 / C++] 테트로미노

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

14500번: 테트로미노

 

문제를 보자마자 생각한건 테트리스였지만, 이번에는 게임에 관련된 문제는 아니였다.

 

문제는 간단하다. 문제의 그림의 테트로미노를 회전시키든 대칭시키든 주어진 숫자 종이위에 배치했을 때, 테트로미노의 숫자의 합의 최대값을 구하는 문제다.

 

테트로미노

 

그렇지만 나는 이 테트로미노 그림이 함정이자 힌트라고 생각한다.

 

다른 사람들은 어떻게 풀었는지 모르지만 내가 처음 생각했을 때는 주어진 그림의 도형을 어떻게 구현해야 할까? 어떻게 대칭, 회전한 것들을 모아볼 수 있을까? 라고 거의 20분넘게 고민했다. 

 

그러다보면 정말 어떤 좌표 y, x에 대해서 테트로미노들의 대칭, 회전 모습을 빡구현해서 합을 구해야하나? 라는 생각이 자연스럽게들었다. 근데 난 빡구현을 정말 못한다. 솔직히 짜증난다.

 

문제를 다시 찬찬히 읽어보면 이런 설명이 있다.

 

 

엥? 정사각형 4개를 이어 붙인 폴리오미노가 테트로미노라고? 그럼 그냥 어떤 좌표 y, x를 기준으로 dfs를 해서 4칸을 차지하면 되는거아니야?

 

그리고 이 아이디어를 잘 생각해보면 테트로미노들의 대칭, 회전된 도형의 모습또한 자연스럽게 구할 수 있다. 왜? 대칭, 회전한 테트로미노들도 결국 블록이 4개가 될 때까지 dfs를 한 것이니까.

 

단! 마지막 보라색 ㅗ 모양을 빼고!!!

 

이 도형은 dfs의 형태가 아니기 때문에 이거에 한해서만 다른 풀이를 생각해야 했다. 내 결론은 그냥

 

이렇게 십자 블록을 그려보면 중심 y, x를 기준으로 딱 한 방향으로의 블록만 제외하고 넓이를 구하는 bfs 풀이를 생각해냈다.

 

코드는 다음과 같다.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, a[504][504], visited[504][504], ret;

void go(int y, int x, int sum, int cnt){ // dfs로 4칸 확인하기
	if(cnt == 4){
		ret = max(ret, sum);
		return;
	}
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if(visited[ny][nx]) continue;
		visited[ny][nx] = 1;
		go(ny, nx, sum + a[ny][nx], cnt + 1);
		visited[ny][nx] = 0;
	}
	return;
}

void go2(int y, int x){ // ㅗ 모양 구하기
	for(int j = 0; j < 4; j++){
		int ans = a[y][x];
		for(int i = 0; i < 4; i++){
			if(i == j) continue;
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			ans += a[ny][nx];
		}
		ret = max(ret, ans);
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			visited[i][j] = 1;
			go(i, j, a[i][j], 1);
			visited[i][j] = 0;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			go2(i, j);
		}
	}
	cout << ret << "\n";
}

 

*참고

1. dfs를 이용해 블록의 넓이를 구한 go 함수는 백트래킹을 하기 때문에 visited[ ][ ]의 방문처리가 자동으로 해제된다. 만약 이를 망각하고 main함수에서 go 함수를 호출할 때마다 visited 배열을 초기화하는 작업을 추가하면 시간초과가 난다.

 

2. 맨 처음 go2 함수를 백트래킹처럼 구현했다가 80% 틀렸습니다가 발생했던 코드

void go2(int y, int x){
	int ans = a[y][x];
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		ans += a[ny][nx];
	}

	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		ret = max(ret, ans - a[ny][nx]);
	}
	return;
}

 

반례를 진짜 오랫동안 생각해봤는데 반례는 첫번째 for문을 거칠 때 십자 모양이 아니라 ㅗ 모양의 넓이를 정확하게 구해버리면 ret = max(ret, ans - a[ny][nx])가 반드시 구해야하는 최대값보다 작은 값을 구하게 된다. 즉,

 

void go2(int y, int x){
	int ans = a[y][x];
	int cnt = 0;
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		ans += a[ny][nx];
		cnt++;
	}
	if(cnt < 4){
		ret = max(ret, ans);
	}
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		ret = max(ret, ans - a[ny][nx]);
	}
	return;
}

 

cnt 조건을 추가해서 첫번째 for문에서 ㅗ모양의 넓이를 정확하게 구해버리는 경우까지 ret = max(ret, ans)를 해주어 최대값을 계산해주어야 한다.

 

시간 초과는 참고 1번, 틀렸습니다의 반례는 2번...