[BOJ_14500] 테트로미노 (골드 4) - JAVA

---

🐾 알고리즘

• 구현
• 브루트포스알고리즘
• DFS(깊이 우선 탐색)
• 4방 탐색 

 

---

🐾 생각 포인트

• 총 5가지의 테트로미노 중 한가지 테트로미노 (ㅗ)자모양빼고는 동일한 방식으로 최댓값을 구할 수 있다. 
• 이거 구분해 내는 것이 가장 난이도가 있었던 부분인 것 같다. 
• DFS 구현시에는 인자에 cnt와 ans값을 넣어주어서 메소드가 실행될 때마다 증가할 수 있도록 하였다.
• 그리고 초기화를 잘해줘야한다. 방문처리 해줄때, 백트래킹처럼 방문처리했던 거를 다시 번복하는 과정을 할 때 주의해야한다는 점....!!!!!

 

---

🐾 소스코드

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

public class Main_14500 {
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int N, M, cnt;
	static int[][] map;
	static int ans;
	static int max = Integer.MIN_VALUE;
	static boolean[][] visited;

	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];
		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++) {
				//ㅗ자 모양이 아닌 경우의 테트로미노
				visited[i][j] = true;
				dfs(i, j, 1, map[i][j]);
				visited[i][j] = false;
				//ㅗ자 모양의 테트로미노가 네가지 종류로 회전하는 경우
				int sum = map[i][j];
				if (i - 1 >= 0 && j - 1 >= 0 && j + 1 < M) {
					sum += map[i - 1][j] + map[i][j - 1] + map[i][j + 1];
					max = Math.max(max, sum);
				}
				sum = map[i][j];
				if (j - 1 >= 0 && j + 1 < M && i + 1 < N) {
					sum += map[i][j - 1] + map[i][j + 1] + map[i + 1][j];
					max = Math.max(max, sum);
				}
				sum = map[i][j];
				if (i - 1 >= 0 && j - 1 >= 0 && i + 1 < N) {
					sum += map[i - 1][j] + map[i][j - 1] + map[i + 1][j];
					max = Math.max(max, sum);
				}
				sum = map[i][j];
				if (i - 1 >= 0 && i + 1 < N && j + 1 < M) {
					sum += map[i - 1][j] + map[i + 1][j] + map[i][j + 1];
					max = Math.max(max, sum);
				}
				
			}
		}
		System.out.println(max);

	}

	private static void dfs(int r, int c, int cnt, int ans) {
		// 기저조건
		if (cnt == 4) {
			max = Math.max(max, ans);
			return;
		}

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
				if (!visited[nr][nc]) {
					visited[nr][nc] = true;
//					System.out.println(map[nr][nc]);
					dfs(nr, nc, cnt + 1, map[nr][nc] + ans);
					visited[nr][nc] = false;
				}
			}

		}

	}
}

---

😵‍💫 공부해야 할 점

• 구현하기 어려운 문제를 쉽게 구현해내는 방법,, 그냥 구현 문제를 많이 풀어봐야겠다.
• 다른 풀이들도 찾아보자..