[BOJ] 14500: 테트로미노 (JAVA)

문제

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

 

풀이

각 칸에서 DFS 탐색을 이용해서 4개 칸을 선택한 뒤, 선택한 배열의 합 중 최댓값을 찾으면 된다.

 

그냥 DFS 탐색을 이용해서 4개의 칸을 선택하면 ㅗ 모양을 처리할 수 없다는 문제가 발생한다. 그래서 총 2가지 방법을 사용해서 문제를 풀었다. 

 

풀이 1

첫 번째 방법은 DFS 탐색을 이용해서 3개의 칸을 선택한 뒤, 선택한 칸 주변의 칸 중 하나를 선택해서 최댓값을 고르는 것이다. 

파란색: DFS로 선택한 칸, 빨간색: 선택한 칸 주변 칸 중 선택 가능한 칸

 

그러나 이 방법은 메모리를  너무 많이 잡아 먹어서 정석 풀이가 아닌 것 같다ㅎ..

메모리 차이 무슨일..? (아래: 풀이1, 위: 풀이2)

 

풀이 2

두 번째 방법은 DFS 탐색을 이용해서 4개의 칸을 선택하고, DFS 탐색만으로 처리하지 못하는 ㅗ 방향을 따로 만들어서 확인해 주는 것이다. 이때, 회전과 대칭시킬 수 있으므로 ㅜ, ㅏ, ㅓ 방향도 따로 확인해야 한다.

 

자세한 내용은 코드로 확인하면 된다.

 

코드

풀이 1

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

public class BOJ_14500 {

	static int N, M, ans;
	static int[][] arr;
	static Point[] points;
	static boolean[][] visited;
	static int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };

	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());
		arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

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

	static void dfs(int depth, int total, int x, int y) {
		// 3개 칸을 고른 경우
		if (depth == 3) {
			// 나머지 칸 고르기
			ans = Math.max(ans, total + bfs());
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny])
				continue;

			visited[nx][ny] = true;
			points[depth] = new Point(nx, ny);
			dfs(depth + 1, total + arr[nx][ny], nx, ny);
			visited[nx][ny] = false;
		}
	}

	static int bfs() {
		int max = 0;
		for (int i = 0; i < 3; i++) {
			Point now = points[i];
			for (int j = 0; j < 4; j++) {
				int nx = now.x + dx[j];
				int ny = now.y + dy[j];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny])
					continue;

				// 선택할 공간의 값이 더 큰 것으로 선택하기
				max = Math.max(max, arr[nx][ny]);
			}
		}
		return max;
	}

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

풀이 2

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

public class BOJ_14500_2 {

	static int N, M, ans;
	static int[][] arr;
	static boolean[][] visited;
	static int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };

	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());
		arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = true;
				dfs(1, arr[i][j], i, j);
				visited[i][j] = false;

				// ㅗ 방향 고려하기
				checkExtraDir(i, j);
			}
		}
		System.out.println(ans);
	}

	static void dfs(int depth, int total, int x, int y) {
		// 네 개의 칸을 고르면 최댓값 갱신하기
		if (depth == 4) {
			ans = Math.max(ans, total);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny])
				continue;

			visited[nx][ny] = true;
			dfs(depth + 1, total + arr[nx][ny], nx, ny);
			visited[nx][ny] = false;
		}
	}

	static void checkExtraDir(int x, int y) {
		// ㅗ 모양
		if (x - 1 >= 0 && y + 2 < M) {
			ans = Math.max(ans, arr[x][y] + arr[x][y + 1] + arr[x][y + 2] + arr[x - 1][y + 1]);
		}

		// ㅜ 모양
		if (x + 1 < N && y + 2 < M) {
			ans = Math.max(ans, arr[x][y] + arr[x][y + 1] + arr[x][y + 2] + arr[x + 1][y + 1]);
		}

		// ㅏ 모양
		if (x + 2 < N && y + 1 < M) {
			ans = Math.max(ans, arr[x][y] + arr[x + 1][y] + arr[x + 2][y] + arr[x + 1][y + 1]);
		}
		// ㅓ 모양
		if (x + 2 < N && y - 1 >= 0) {
			ans = Math.max(ans, arr[x][y] + arr[x + 1][y] + arr[x + 2][y] + arr[x + 1][y - 1]);
		}
	}
}

 

여담

소프티어에 나온 문제와 결이 비슷한 문제인 것 같다. DFS로 만들 수 있는 모양의 예외를 잘 생각했더라면 통과됐을 가능성이 있지 않을까,,라는 생각이 들지만 뭐.. 몰라서 틀렸던 것에는 크게 집착하지 않으려고 한다. 대신 이런 문제가 다시 나왔을 때는 절대로 틀리면 안된다...! 

---