[백준] 14500번: 테트로미노

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

14500번: 테트로미노

 

문제 이해

처음엔 500*500 (맵사이즈) * 5 (테트로미노 종류) * 4 (돌리는 거) 를 다 해봐야 해? 라고 생각해서 기겁했던 문제이다.

다 방향벡터로 만들어서 해야하나? 생각했다가 그냥 5개 테트로미노들에 대해 모든 좌표를 적용해보자 하고, 두 번째 테트로미노까지 구현했다가, 이건 아닌데... 싶어서 인터넷 검색을 했다.

 

1번부터 4번 테트로미노까지는 DFS로 처리하면 되고, DFS로 처리가 안되는 ㅜ 자 모양 테트로미노만 약간의 노가다를 하면 되는 문제였다.

 

1번 ~ 4번 테트로미노 처리 (Tetromino1234())

처음에 이걸 DFS로? 했는데,

한 좌표에서 사방탐색을 4번하면서, 하나씩 골라 이으면 테트로미노 1~4중에 한 모양이 나온다!

이런식으로 말이다.

 

주의할 점은, 이것도 DFS니까 당연히 visited를 사용해야 한다!!

한 번 DFS하고 돌아오면 visited를 다시 0으로 바꿔주기만 하면 된다.

그리고 depth는 4가 아닌 3이다. 왜냐하면 시작 좌표는 당연 1이고, 그 이후의 2, 3, 4번 좌표를 정하기만 하면 되니까.

void Tetromino1234(void) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			// 이 좌표에서 4방향으로 이어진 4개 블럭들 다 구하면 됨
			visited[i][j] = 1;
 			DFS(i, j, 0, map[i][j]);
			visited[i][j] = 0;
		}
	}
}

void DFS(int y, int x, int cnt, int sum) {
	// 종료
	if (cnt == 3) {
		if (sum > max) max = sum;
		return;
	}

	// 재귀
	for (int i = 0; i < 4; i++) {
		int ny = dy[i] + y;
		int nx = dx[i] + x;
		if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if (visited[ny][nx] == 1) continue;
		visited[ny][nx] = 1;
		DFS(ny, nx, cnt + 1, sum + map[ny][nx]);
		visited[ny][nx] = 0;
	}
}

 

5번 테트로미노 (Tetromino5())

이건 일종의 방향 벡터를 만들어서 처리해줬다.

ㅗ 모양은 총 4가지가 가능하다:

그래서

0인 경우 현재좌표 + 상우좌를 더하도록 하고,

1인 경우 현재좌표 + 상우하 를 더하도록...

 

이런 식으로 dir이라는 배열에 정해줬다.

그리고 4중 for문으로 처리했다

void Tetromino5(void) {
	static int dir[4][4] = {
		{1, 0, 1, 1}, // 상.좌우
		{1, 1, 0, 1 }, // 상하.우
		{0, 1, 1, 1}, // .하좌우
		{1, 1, 1, 0}, // 상하좌.
	};
	int ny, nx, flag;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 4; k++) { // 네 가지 경우
				int sum = map[i][j];
				flag = 1;
				for (int l = 0; l < 4; l++) { // 네 가지 방향 체크
					if (dir[k][l] == 1) {
						ny = i + dy[l], nx = j + dx[l];
						if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
							flag = 0;
							break;
						}
						sum += map[ny][nx];
					}
				}
				if (!flag) continue;
				if (sum > max) max = sum;
			}
		}
	}
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXMN 500

int N, M;
int map[MAXMN + 5][MAXMN + 5];
int visited[MAXMN + 5][MAXMN + 5];
int max;

void Get_Input(void) {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

int dy[] = { -1, 1, 0, 0 }; // 상하좌우
int dx[] = { 0, 0, -1, 1 };

void DFS(int y, int x, int cnt, int sum) {
	
	// 종료
	if (cnt == 3) {
		if (sum > max) max = sum;
		return;
	}

	// 재귀
	for (int i = 0; i < 4; i++) {
		int ny = dy[i] + y;
		int nx = dx[i] + x;
		if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if (visited[ny][nx] == 1) continue;
		visited[ny][nx] = 1;
		DFS(ny, nx, cnt + 1, sum + map[ny][nx]);
		visited[ny][nx] = 0;
	}
}

void Tetromino1234(void) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			// 이 좌표에서 4방향으로 이어진 4개 블럭들 다 구하면 됨
			visited[i][j] = 1;
 			DFS(i, j, 0, map[i][j]);
			visited[i][j] = 0;
		}
	}
}

void Tetromino5(void) {
	static int dir[4][4] = {
		{1, 0, 1, 1}, // 상.좌우
		{1, 1, 0, 1 }, // 상하.우
		{0, 1, 1, 1}, // .하좌우
		{1, 1, 1, 0}, // 상하좌.
	};
	int ny, nx, flag;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 4; k++) { // 네 가지 경우
				int sum = map[i][j];
				flag = 1;
				for (int l = 0; l < 4; l++) { // 네 가지 방향 체크
					if (dir[k][l] == 1) {
						ny = i + dy[l], nx = j + dx[l];
						if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
							flag = 0;
							break;
						}
						sum += map[ny][nx];
					}
				}
				if (!flag) continue;
				if (sum > max) max = sum;
			}
		}
	}
}

int main(void) {
	Get_Input();
	Tetromino1234();
	Tetromino5();
	printf("%d", max);
	return 0;
}