[백준] 14500.테트로미노 (java) / 백트래킹, DFS

@백트래킹, DFS / 20m (6m 필기 포함)

예전에 두번 풀어봤던거라 풀이법을 알고 있어서 금방 풀었다(거의 외워서 푼 수준..ㅎ)

그렇지만 예전보다 더 간단하게 풀었다는 것에 의의를..

 

 

 

문제 링크

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

14500번: 테트로미노

 

 

 

구현 포인트

기본적으로 백트래킹과 DFS, visit을 사용해서 풀면 되는 문제이다.

문제는 이 모양의 폴리오미노인데, 이 모양은 일반적인 백트래킹으로는 구현할 수 없다

(왜냐하면 step 2번째에서 두갈래로 뻗어나와야 하기 때문에)

그래서 이 경우를 위해서, step == 2일 때만 한번 더 다른 점을 탐색하도록 코드를 구현했다

이 부분만 처리하면 매우 쉬운 문제였다

 

 

 

 

문제 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	private static int N, M, max = Integer.MIN_VALUE, map[][];
	private static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	private static boolean[][] visit;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visit = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) 
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		
		findStart();
		System.out.println(max);
	}

	private static void findStart() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visit[i][j] = true;
				backTracking(i, j, map[i][j], 1);
				visit[i][j] = false;
			}
		}
	}

	private static void backTracking(int x, int y, int sum, int step) {
		if (step == 4) {
			if (max < sum) max = sum;
			return;
		}
		
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= M || visit[nx][ny])
				continue;
			
			visit[nx][ny] = true;
			backTracking(nx, ny, sum + map[nx][ny], step + 1);
			
			if (step == 2) {	//T자 모양으로 된 폴리오미노를 위해서 
				for (int d2 = 0; d2 < 4; d2++) {
					int nx2 = x + dx[d2];
					int ny2 = y + dy[d2];
					
					if (nx2 < 0 || nx2 >= N || ny2 < 0 || ny2 >= M || visit[nx2][ny2])
						continue;
					
					visit[nx2][ny2] = true;
					backTracking(nx2, ny2, sum + map[nx][ny] + map[nx2][ny2], step + 2);
					visit[nx2][ny2] = false;
				}
			}
			
			visit[nx][ny] = false;
		}
	}
}

 

 

예전에 풀었을 때에는, 이전의 x, y 좌표를 들고 다니면서 step이 3일 때 그 이전 좌표들을 이용해서 처리하도록 구현했는데,

이번에 푼 코드가 가독성도, 효율 측면에서도 더 나은 것 같다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

static int n, m, maxSum = -1, map[][];
static int[] dx = {0, -1, 0, 1};
static int[] dy = {-1, 0, 1, 0};
static boolean[][] visit;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

map = new int[n][m];
visit = new boolean[n][m];

for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}

findStarting();
System.out.println(maxSum);
}

private static void findStarting() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visit[i][j]) {
visit[i][j] = true;
dfs(i, j, -1, -1, 1, map[i][j]);
visit[i][j] = false;
}
}
}
}

private static void dfs(int x, int y, int prex, int prey, int depth, int sum) {
if (depth >= 4) {
if (maxSum < sum) maxSum = sum;
return;
}

int nx, ny;
for (int d = 0; d < 4; d++) {
nx = x + dx[d];
ny = y + dy[d];

if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny])
continue;

visit[nx][ny] = true;
dfs(nx, ny, x, y, depth + 1, sum + map[nx][ny]);
visit[nx][ny] = false;
}

//산모양 테트리스 해결을 위해서
if (depth == 3) {
for (int d = 0; d < 4; d++) {
nx = prex + dx[d];
ny = prey + dy[d];

if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny])
continue;

visit[nx][ny] = true;
dfs(nx, ny, prex, prey, depth + 1, sum + map[nx][ny]);
visit[nx][ny] = false;
}
}
}
}

 

 

 

 

무난한 문제지만 백트래킹을 이해하는 데 좋은 문제라고 생각한다.

 

끝!