14500번 - 테트로미노

1️⃣ DFS

 

✏️ 풀이 과정

1위 코드를 보니 구현으로 해결하는 문제였지만 DFS를 이용해서 성능을 희생하는 대신 좀 더 코드 길이를 줄일 수 있습니다.

 

기본적인 아이디어는 테트로미노는 4칸이 연결되어 있는 모든 경우의 수에 해당하기 때문에 NxM의 각 칸마다 DFS를 돌려서(n이 4가 될 때 까지만) 최댓값을 갱신하는 것입니다.

 

저도 틀리고 나서 알았지만 이 아이디어에는 문제가 두 개 있는데 한 가지는 중복 계산이 일어난다는 것과(시작 부분과 끝 부분 2번 혹은 사각형 테트로미노의 경우 4번까지 중복됩니다.) T자형 테트로미노를 계산하지 못한다는 것입니다. 그 이유는 DFS 혹은 BFS를 통해 4단계까지 돌린다고 가정하면 T자형은 최종 단계에서 나타나는 게 아니라 중간 분기로만 볼 수 있기 때문입니다. 그리고 등장해도 각각 다른 결과로 분기하기 때문에 T자형의 결과를 파악할 수 없습니다.

 

이를 해결하기 위해 아래 코드에서는 전체를 순회하며 DFS를 돌리는 동시에 T자형만 찾는 코드를 포함하여 모든 경우의 수를 셀 수 있도록 만들었습니다.

 

각 도형이 완성될 때마다 max값이 갱신되기 때문에 전체 행렬 순회가 끝나면 max값을 출력하면 됩니다.

 

💻 코드

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

public class Main {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static int[][] map;
	
	static int max, N, M;
	
	static boolean[][] inner;
	
	static void dfs(int n, int sum, int r, int c) {
		if(n == 4) {
			if(sum > max) {
				max = sum;
			}
			return;
		}
		int nr, nc;
		for(int i=0;i<4;i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			if(nr>=0 && nc>=0 && nr<N && nc<M && !inner[nr][nc]) {
				inner[nr][nc] = true;
				dfs(n+1, sum+map[nr][nc], nr, nc);
				inner[nr][nc] = false;
			}
		}
	}
	
	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];
		inner = new boolean[N][M];
		max = Integer.MIN_VALUE;
		int sum, nr, nc;
		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());
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				inner[i][j] = true;
				dfs(1, map[i][j], i, j);
				inner[i][j] = false;
				for(int k=0;k<4;k++) {
					sum = map[i][j];
					for(int l=0;l<4;l++) {
						if(l == k) {
							continue;
						}
						nr = i + dr[l];
						nc = j + dc[l];
						if(nr>=0 && nc>=0 && nr<N && nc<M) {
							sum += map[nr][nc]; 
						}
					}
					if(sum > max) {
						max = sum;
					}
				}
			}
		}
		System.out.println(max);
		br.close();
	}
}