삼성 코딩테스트 기출_(백준)테트로미노

난이도 ★★☆

 

문제출처

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

14500번: 테트로미노

포인트

1. dfs

1-1. 테트로미노는 칸의 개수가 네 개로 제한된 dfs로 구현한다. dfs가 진행될 때마다 map[][]에 쓰여져 있는 숫자를 더해주는데, 중요한 것은, dfs가 리턴될 때마다는 그 숫자를 다시 빼줘야 한다는 점이다.

1-2. 또한, 칸의 개수를 4개로 제한하는 것은 cnt=4에서 시작해서 dfs를 진행할 때마다 cnt--를 해주는 방식으로 구현한다.

1-3. dfs가 끝날 때에는 cnt역시 하나 늘려주어야 한다는 점을 주의한다.

1-4. dfs가 끝날 때에는 visit[][]을 그때그때 초기화해준다.

 

2. ㅓ, ㅗ, ㅏ, ㅜ

테트로미노 중 dfs로 구현되지 않는 모양이 있다. 바로 'ㅗ' 모양과 이를 대칭 및 회전시킴으로써 생겨나는 모양들이다. 따라서 이 네 가지 모양에 대해서는 별도로 구현해준다.

(map[][]에서 벗어나지 않도록 범위만 잘 체크해주면 구현은 어렵지 않음)

 

3. main에서 계속 초기화

main에서는 위에 언급한 1. dfs와 2. ㅓ,ㅗ,ㅏ,ㅜ를 반복적으로 호출한다. 전역변수로 선언된 ans의 값이 변화되어 있는 상태이므로 호출 전에 ans 값을 0으로 초기화하는 작업이 필요하다. cnt역시 4로 초기화하는 작업을 해야한다.

 

정답코드

#include <iostream>
using namespace std;

int n, m;
int map[550][550];
int visit[550][550];

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

int cnt = 4; //dfs로 진행할 테트로미노 칸의 개수 세기
int realAns = 0;//최종 답이 저장될 변수
int ans = 0; //매 회 dfs 및 ㅓ,ㅗ,ㅏ,ㅜ 호출 때마다 갱신되는 임시 답

void dfs(int r, int c) {//ㅓ,ㅗ,ㅏ,ㅜ를 제외한 나머지 테트로미노 구현
	cnt--;//블록 개수 하나 카운트
	visit[r][c] = 1;//방문 표시
	ans += map[r][c];//칸에 적힌 수 더해주기

	if (cnt == 0) { //만약 네 개의 칸을 다 방문했다면(테트로미노 완성됨)
		if (ans > realAns) realAns = ans; //정답 갱신
		return;
	}

	for (int i = 0; i < 4; i++) {//상,하,좌,우를 순회하며 dfs
		int nr = r + dy[i];
		int nc = c + dx[i];
		if (nr >= 0 && nr < n && nc >= 0 && nc<m && !visit[nr][nc]) {
			dfs(nr, nc);
			cnt++;//dfs 리턴 후에는 cnt 하나 늘려주고
			ans -= map[nr][nc];//해당 칸에 적힌 수 빼주기
			visit[nr][nc] = 0;//방문 초기화해주기
		}
	}
	visit[r][c] = 0;

	return;
}

void oh(int r, int c) {//'ㅗ' 모양은 따로 구현
	ans = 0;
	int firstR = r;
	int firstC = c;

	int secondR = r;
	int secondC = c + 1;

	int thirdR = r;
	int thirdC = c + 2;

	int fourthR = r - 1;
	int fourthC = c + 1;

	if (firstR >= 0 && firstR < n&&secondR >= 0 && secondR < n&&thirdR >= 0 && thirdR < n&&fourthR >= 0 && fourthR < n&&firstC >= 0 && firstC < m&&secondC >= 0 && secondC < m&&thirdC >= 0 && thirdC < m&&fourthC >= 0 && fourthC < m) {
		ans += map[firstR][firstC];
		ans += map[secondR][secondC];
		ans += map[thirdR][thirdC];
		ans += map[fourthR][fourthC];
	}
	else return;
	if (ans > realAns)realAns = ans;
	ans = 0;
}

void uh(int r, int c) { //'ㅓ'
	ans = 0;
	int firstR = r;
	int firstC = c;

	int secondR = r+1;
	int secondC = c;

	int thirdR = r+2;
	int thirdC = c;

	int fourthR = r+1;
	int fourthC = c-1;

	if (firstR >= 0 && firstR < n&&secondR >= 0 && secondR < n&&thirdR >= 0 && thirdR < n&&fourthR >= 0 && fourthR < n&&firstC >= 0 && firstC < m&&secondC >= 0 && secondC < m&&thirdC >= 0 && thirdC < m&&fourthC >= 0 && fourthC < m) {
		ans += map[firstR][firstC];
		ans += map[secondR][secondC];
		ans += map[thirdR][thirdC];
		ans += map[fourthR][fourthC];
	}
	else return;
	if (ans > realAns)realAns = ans;
	ans = 0;
}

void ooh(int r, int c) {//'ㅜ'
	ans = 0;
	int firstR = r;
	int firstC = c;

	int secondR = r;
	int secondC = c+1;

	int thirdR = r;
	int thirdC = c+2;

	int fourthR = r + 1;
	int fourthC = c +1 ;

	if (firstR >= 0 && firstR < n&&secondR >= 0 && secondR < n&&thirdR >= 0 && thirdR < n&&fourthR >= 0 && fourthR < n&&firstC >= 0 && firstC < m&&secondC >= 0 && secondC < m&&thirdC >= 0 && thirdC < m&&fourthC >= 0 && fourthC < m) {
		ans += map[firstR][firstC];
		ans += map[secondR][secondC];
		ans += map[thirdR][thirdC];
		ans += map[fourthR][fourthC];
	}
	else return;
	if (ans > realAns)realAns = ans;
	ans = 0;
}

void ah(int r, int c) {//'ㅏ'
	ans = 0;
	int firstR = r;
	int firstC = c;

	int secondR = r + 1;
	int secondC = c;

	int thirdR = r + 2;
	int thirdC = c;

	int fourthR = r + 1;
	int fourthC = c +1 ;

	if (firstR >= 0 && firstR < n&&secondR >= 0 && secondR < n&&thirdR >= 0 && thirdR < n&&fourthR >= 0 && fourthR < n&&firstC >= 0 && firstC < m&&secondC >= 0 && secondC < m&&thirdC >= 0 && thirdC < m&&fourthC >= 0 && fourthC < m) {
		ans += map[firstR][firstC];
		ans += map[secondR][secondC];
		ans += map[thirdR][thirdC];
		ans += map[fourthR][fourthC];
	}
	else return;
	if (ans > realAns)realAns = ans;
	ans = 0;
}

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cnt = 4;
			ans = 0;//cnt와 ans는 계속 초기화
			dfs(i, j);
			oh(i, j);
			uh(i, j);
			ooh(i, j);
			ah(i, j);
		}
	}

	cout << realAns << '\n';

	return 0;
}