[BOJ 14500] 테트로미노 (C++)

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

14500번: 테트로미노

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int graph[500][500];

struct mino{
	int sum;
	int cnt;
	int py, px;
	int y,x;
};

int bfs(int y, int x, int N, int M){
	int ans=0;
	queue<mino> q;
	q.push({graph[y][x], 1, -1, -1, y, x});
	while (!q.empty()){
		mino m=q.front(); q.pop();
		if (m.cnt==4){
			ans=max(ans, m.sum);
			continue;
		}
		for (int i=0; i<4; i++){
			int ny=m.y+dy[i]; 
			int nx=m.x+dx[i];
			if (ny<0 || nx<0 || ny>=N || nx>=M)
				continue;
			if (ny==m.py && nx==m.px)
				continue;
			q.push({m.sum+graph[ny][nx], m.cnt+1, m.y, m.x, ny, nx});
		}
	}
	return ans;
}

int except_(int y, int x, int N, int M){
	int minVal=1001;	//제일 작은 값 빼준다
	int cnt=0;
	int ans=graph[y][x];
	for (int i=0; i<4; i++){
		int ny=y+dy[i];
		int nx=x+dx[i];
		if (ny<0 || nx<0 || ny>=N || nx>=M)
			continue;
		cnt++;
		minVal=min(minVal, graph[ny][nx]);
		ans+=graph[ny][nx];
	}
	if (cnt==3)
		return ans;
	else if (cnt==4)
		return ans-minVal;
	else
		return 0;
}

int main(){
	int N, M;
	int answer=0;
	cin>>N>>M;
	for (int i=0; i<N; i++){
		for (int j=0; j<M; j++){
			cin>>graph[i][j];
		}
	}
	for (int i=0; i<N; i++){
		for (int j=0; j<M; j++){
			answer=max(bfs(i,j,N,M),answer);
			//exception 처리(ㅗ 모양)
			answer=max(except_(i,j,N,M), answer);
		}
	}
	cout<<answer<<"\n";
	return 0;
}

이것 역시 처음에 큐를 한번만 써서 해결하려다가 자꾸 꼬여서.. 힌트를 보고 풀었다.

나는 bfs로 풀었으나 재귀 사용해서 dfs 이용해서 탐색해줘도 된다.

 

모양은 "테트로미노"이나 잘 살펴보면 이 모양이 서로 인접한 사각형들의 모임임을 알 수 있다. 즉 bfs 로 인접한 애들을 모두 탐색하면 된다는 뜻. 그런데 여기서 함정은 'ㅗ' 이 모양은 bfs나 dfs로 탐색 불가능하다. 이 모양 같은 경우에는 따로 빼줘서 계산해줘야 된다.

 

우선 모든 좌표에 대해 bfs 탐색을 돌려 가능한 모든 경우의 수를 탐색한다.

큐에는 부모 좌표도 같이 저장해서 왔던 길을 또 되돌아가는 일이 없게 한다. 즉 next 좌표와 부모 좌표가 같으면 그것은

탐색하지 않는다. 

탐색한 좌표가 4개가 되면 값을 계산한다.(테트로미노니까 4개)

 

'ㅗ' 모양은 except_ 로 구현했다. '+'  모양이 나올 때는 여기서 인접한 좌표들 중 최소값을 갖는 애를 합에서 빼준다.

'ㅗ' 모양 나올 때는 그대로 그 합들을 리턴하면 된다. 'ㅗ' 모양은 bfs 로 탐색 불가능하기 때문에 수동으로 해줘야된다.

 

2가지 탐색(bfs 탐색, 'ㅗ' 탐색)을 모든 좌표에 대해 돌려주고 최대값을 구해주면 된다. 

 

ㅗ 모양을 잘 보고 이건 bfs 탐색으로 불가능한 케이스임을 캐치하는 게 중요했다.

그리고 복잡하게 생각말고 각 좌표별로 bfs 돌리자.. 그래봤자 시간복잡도 O(M*N*4**3) 으로 충족된다.

괜히 처음에 visited 배열 여러개 만들고 그랬다.... 다시 온 길을 안되돌아 갈려면 부모 좌표를 큐에 같이 저장해서 다음 좌표가 부모 좌표와 같은지만 체크해주면 된다.