[백준] 14500번 테트로미노 - C/C++ (Easy 풀이)

백준 14500 문제(Problem)

 

백준 14500 문제

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

 

풀이 & 전체 코드(Solution & Code)

풀이)

dfs 코드를 기반으로 추가 구현 코드를 작성하면 쉽게 풀 수 있는 문제이다. 필자는 side_dfs 함수를 추가로 구현하여 문제를 풀었는데, 'ㅗ, ㅓ, ㅜ, ㅏ' 와 같이 4가지의 경우는 dfs만으로 구현할 수 없기에 side_dfs 함수로 이를 추가 구현하였다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, map[501][501], res, visited[501][501];

// 인접한 두 셀 (x1, y1)과 (x2, y2)의 값을 더해서 합산하는 함수
void side_dfs(int x1, int y1, int x2, int y2, int sum) {
	if(x1<0 || x1>=m || y1<0 || y1>=n) return ;
	if(x2<0 || x2>=m || y2<0 || y2>=n) return ;
	if(visited[y1][x1] || visited[y2][x2]) return;

	sum += (map[y1][x1]+map[y2][x2]);
	res = max(sum, res);
}

// DFS를 이용하여 테트로미노를 놓을 수 있는 모든 경우를 탐색하는 함수
void dfs(int depth, int sum, int x, int y) {
	if(x<0 || x>=m || y<0 || y>=n) return ;
	if(visited[y][x]) return;
	sum += map[y][x];
	if(depth == 4) {
		res = max(res, sum);
		return;
	}
	visited[y][x]=1;

	if(depth==2) {
		// 현재 셀의 인접한 옆 위치를 확인하기 위해 side_dfs 함수 호출
		side_dfs(x-1, y, x+1, y, sum);
		side_dfs(x, y+1, x, y-1, sum);
	}
	
	// 상하좌우 4방향으로 재귀적으로 탐색
	dfs(depth+1, sum, x+1, y);
	dfs(depth+1, sum, x-1, y);
	dfs(depth+1, sum, x, y+1);
	dfs(depth+1, sum, x, y-1);
	visited[y][x]=0;
}

int main() {
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> map[i][j];
		}
	}

	// 각 셀에서 DFS 함수 호출하여 최대 합 계산
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			dfs(1, 0, j, i);
		}
	}
	cout << res;
}