[backjoon]14500 테트로미노 java

www.acmicpc.net/problem/14500

14500번: 테트로미노

문제만 보고는 저거를 다 돌려야하나 귀찮고 막막하다 생각을 했다.

다른 블로그들을 참고하니 ㅜ 모양을 제외하고는 길이가 4인 최단 경로라는 점에서 착안하여 풀이하면 된다고 하였다.

모든 경우를 구해야하기에 백트래킹을 이용하였고,

ㅜ 모양의 경우엔, 한 모양에서 길이가 3인 경우가 최단 경로이기에 따로 분리하여 풀이하였다.

최대 값을 구하기 위해서 백트래킹시에 사용되는 메서드에 현재 위치의 값을 합할 매개변수로 넣어주어 활용하였다.

문제 풀이 발상을 떠올리는게 굉장히 오래 걸리지만, 위와 같은 방법을 통해 풀이한다면 충분히 풀 수 있다.

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

class Main {

	static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}	};
	static boolean[][] marked;
	static int answer, n,m;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		answer = Integer.MIN_VALUE;
		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];
		marked = 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, 0, 0);
				specialCase(i, j);
			}
		}
		System.out.println(answer);
	}
	
	public static void specialCase(int row, int col) {
		int result = Integer.MIN_VALUE;
		int[][][] specialDir = {
				{{0, 0}, {1, 0}, {2, 0}, {1, 1}},
				{{1, 0}, {0, 1}, {1, 1}, {2, 1}},
				{{0, 1}, {1, 0}, {1, 1}, {1, 2}},
				{{0, 0}, {0, 1}, {0, 2}, {1, 1}}
		};
		
		for (int[][] cur : specialDir) {
			int sum = 0;
			for (int i = 0; i < 4; i++) {
				int nextR = row + cur[i][0];
				int nextC = col + cur[i][1];
				if(nextR < 0 || nextC < 0 || nextR >= n || nextC >= m) continue;
				sum += map[nextR][nextC];
			}
			result = Math.max(result, sum);
		}
		answer = Math.max(answer, result);
	}
	
	public static void dfs(int row, int col, int sum, int length) {
		if(length == 4) {
			answer = Math.max(sum, answer);
			return;
		}
		for (int i = 0; i< 4; i++) {
			int nextR = row + dirs[i][0];
			int nextC = col + dirs[i][1];
			
			if(nextR < 0 || nextC < 0 || nextR >= n || nextC >= m) continue;
			if(marked[nextR][nextC]) continue;
			
			marked[nextR][nextC] = true;
			dfs(nextR, nextC, sum + map[nextR][nextC], length +1);
			marked[nextR][nextC] = false;
		}
	}
}