백준_14500 테트로미노(자바) / DFS + 예외/브루트포스

시간 & 메모리 제한

문제

입력 & 출력

예제

DFS + 예외를 이용한 문제풀이

package com.Back;

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

public class Back_14500 {

	static int C, R, ans=0;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	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());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[C][R];
		visited = new boolean[C][R];

		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < R; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < C; i++) {
			for (int j = 0; j < R; j++) {
				dfs(i, j, 0, 0);
				other(i,j);
			}
		}
		System.out.println(ans);
	}

	private static void other(int x, int y) {
		int wing =4;
		int min = Integer.MAX_VALUE;
		int sum = map[x][y];
		for (int k = 0; k < 4; k++) {
			int xx = x+dx[k];
			int yy = y+dy[k];
			
			if(wing<=2)return;
			
			if(xx<0 || xx>=C || yy<0 || yy>=R) {
				wing--;
				continue;
			}
			min = Math.min(min, map[xx][yy]);
			sum = sum + map[xx][yy];
		}
		if(wing == 4) {
			sum = sum - min;
		}
		ans = Math.max(ans, sum); 
	}

	private static void dfs(int x, int y, int depth, int sum) {
		if (depth == 4) {
			ans = Math.max(ans, sum);
			return;
		}

		for (int k = 0; k < 4; k++) {
			int xx = x + dx[k];
			int yy = y + dy[k];
			if (xx < 0 || yy < 0 || xx >= C || yy >= R) {				
				continue;
			}
			if (visited[xx][yy]) {				
				continue;
			}
			visited[xx][yy] = true;
			dfs(xx, yy, depth + 1, sum + map[xx][yy]);
			visited[xx][yy] = false;
		}
	}

}

- 이 문제의 경우 예외 부분때문에 고생을 많이 했습니다... 그래서 다른분들이 푸신것을 참고하여서 풀었습니다.

 

- Step1. 모든 칸에 대해서 DFS를 진행을 해줍니다.

 

- Step2. DFS를 통해서 4방탐색을 진행합니다. 깊이가 4가 되는 순간에 DFS를 멈추고 그때까지 더한 값을 비교해줍니다.

 

- 여기까지는 순조롭게 진행을 했습니다..

 

- ㅓ ㅗ ㅜ ㅏ 의 경우가 DFS로 만들 수 없다는 것을 마지막 예제에서 알게 되었습니다.

 

- 이 부분에 대한 예외처리가 따로 필요했고 함수로 만들어줬습니다.

 

- + 의 모양으로 계산을 했고, 이중에서 4개의 방향중에서 최소인 값을 뺴주는 방식으로 구현을 했습니다.