테트로미노


백준 [14500] 테트로미노

문제보기
Alt text

풀이

테트로미노 탐색은 dfs로 진행하였고, 凸 모양의 테트로미노는 따로 조건처리

  • dfs(int r, int c, int n, int sum, int chk, boolean[][] visited)
  • r, c : 현재 좌표
  • sum : 현재까지의 총 합
  • chk : 凸 모양을 위해 어디서 온 방향인지 체크. 볼록한 부분이 어디로 볼록해져야 할지 정하기 위해.
  • visited : 방문체크

소스코드

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

public class Main {
	static int N, M;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int ans;

	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];

		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());
			}
		}

		ans = 0;
		boolean[][] visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = true;
				dfs(i, j, 1, map[i][j], 0, visited);
				visited[i][j] = false;
			}
		}
		System.out.println(ans);
	}

	public static void dfs(int r, int c, int n, int sum, int chk, boolean[][] visited) {
		if (n == 4) {
			ans = Math.max(ans, sum);
			return;
		}

		if (n == 2) {
			int num1 = 0;
			int num2 = 0;
			int idx = -1;

			switch (chk) {
			case 0:
			case 1:
				num1 = isRange(r + dx[2], c + dy[2]) ? map[r + dx[2]][c + dy[2]] : -1;
				num2 = isRange(r + dx[3], c + dy[3]) ? map[r + dx[3]][c + dy[3]] : -1;
				if (num1 >= num2)
					idx = 2;
				else
					idx = 3;
				break;
			case 2:
			case 3:
				num1 = isRange(r + dx[0], c + dy[0]) ? map[r + dx[0]][c + dy[0]] : -1;
				num2 = isRange(r + dx[1], c + dy[1]) ? map[r + dx[1]][c + dy[1]] : -1;
				if (num1 >= num2)
					idx = 0;
				else
					idx = 1;
				break;
			}
			int num = Math.max(num1, num2);
			if (isRange(r + dx[idx], c + dy[idx]) && num > 0) {
				visited[r + dx[idx]][c + dy[idx]] = true;
				dfs(r, c, n + 1, sum + num, chk, visited);
				visited[r + dx[idx]][c + dy[idx]] = false;
			}
		}

		for (int i = 0; i < 4; i++) {
			int x = r + dx[i];
			int y = c + dy[i];

			if (isRange(x, y) && !visited[x][y]) {
				visited[x][y] = true;
				dfs(x, y, n + 1, sum + map[x][y], i, visited);
				visited[x][y] = false;
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}