[백준] 14500. 테트로미노

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

14500번: 테트로미노

---

입력받은 2차원 배열에서 처음 부터 끝까지 완전탐색하면서 주어진 정사각형 4개를 이어 붙인 테트로미노 영역의 값을 계산해서 최대값을 구하는 문제입니다. 

 

생각해보면 옆의 4가지 도형들은 한쪽에서 시작하는 4방향 DFS를 하면서 depth 가 0부터 3까지 들어가고, 배열의 범위 밖을 벗어나는지 판단하면서 재귀적으로 호출하면 4방향으로 모두 돌려본 테트로미노를 확인 할 수 있습니다.

 

 

 

하지만 옆의 테트로미노는 depth 가 1일 때 두 방향으로 나아가므로 일반적인 DFS로는 4 방향으로 돌려본 테트로미노의 영역에 있는 값을 계산할 수 없기 때문에 위의 4개의 테트로미노와 다른 방법으로 계산 해 주어야 합니다. 그래서 저는 4번 반복하는 2중 반복문을 통해서 한쪽이 없는 테트로미노 영역의 값을 계산해 주었습니다. calc 라는 함수를 보면 쉽게 이해할 수 있습니다.

주의 할 점은 DFS 와 calc 함수를 끝내고 그 자리의 visited를 false로 다시 바꿔주어야 다음 좌표에서 다시 DFS, calc를 수행할 때 돌아간 테트로미노의 영역을 계산할 수 있습니다.

---

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

// 14500 테트로미노
class Main {
	
	static int N, M, answer;
	static int[][] map, dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = 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());
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				DFS(i, j, map[i][j], 0);
				calc(i, j);
				visited[i][j] = false;
			}
		}
		
		System.out.println(answer);
		
	}
	
	public static void calc(int x, int y) {
		
		for(int i=0; i<4; i++) {
			
			int sum = map[x][y];
			boolean flag = true;
			
			for(int j=0; j<4; j++) {
				if(i == j) continue;
				int nx = x + dir[j][0];
				int ny = y + dir[j][1];
				
				if(!isInside(nx, ny)) {
					flag = false;
					break;
				} else sum += map[nx][ny];
			}
			
			if(flag) answer = Math.max(answer, sum);
		}
	}
	
	public static void DFS(int x, int y, int sum, int len) {
		
		visited[x][y] = true;
		
		if(len == 3) {
			answer = Math.max(answer, sum);
			return;
		}
		
		for(int i=0; i<4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny]) {
				DFS(nx, ny, sum + map[nx][ny], len + 1);
				visited[nx][ny] = false;
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<M;
	}
	
}