[백준 / C++] 14500번: 테트로미노 (삼성 SW 역량테스트 기출)

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

14500번: 테트로미노

난이도: solved.ac 골드 4

 

알고리즘 분류

구현, 브루트포스 알고리즘

 

접근 방법 및 구현

ㅗ 모양을 제외한 나머지 모양은 한 지점에서 depth = 4짜리 DFS를 돌리면 구현 가능하다.

신경 써야 할 것은 ㅗ 모양인데, 나는 ㅗ에서 가운데 부분을 기준으로 잡고 상하좌우에서 3개를 골라 그 부분들의 합을 함께 더해주는 식으로 구현했다.

상하좌우에서 3개를 고르는 건 DFS에서 사용한 dy[4]와 dx[4]에서 한 칸을 골라 그 칸만 제외하도록 했다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int space[500][500];
int visited[500][500];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int N, M, ans;
void DFS(int y, int x, int d, int sum);
void T(int y, int x);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int i, j;
	cin >> N >> M;
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			cin >> space[i][j];

	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			DFS(i, j, 1, 0);
			T(i, j);
		}
	}
	cout << ans;
}

void DFS(int y, int x, int d, int sum) {
	sum += space[y][x];
	visited[y][x] = 1;
	if (d == 4) {
		if (sum > ans)
			ans = sum;
		visited[y][x] = 0;
		return;
	}
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
			if (!visited[ny][nx])
				DFS(ny, nx, d + 1, sum);
		}
	}
	visited[y][x] = 0;
}

void T(int y, int x) {
	int sum, dir, ny, nx;
	for (int i = 0; i < 4; i++) {
		sum = space[y][x];
		for (dir = 0; dir < 4; dir++) {
			if (dir == i)
				continue;
			ny = y + dy[dir];
			nx = x + dx[dir];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M)
				sum += space[ny][nx];
		}
		if (sum > ans)
			ans = sum;
	}
}

 

성능

코드 제출 결과