문제 링크

문제 링크

문제 설명

입력

출력

설명

1. 나는 보자마자 DFS가 떠올랐다.
   1-1 최대 4개까지 쭉쭉 뻗어가면서 마지막에 다다른 블록이 마치 꿈틀대며 붙은채로 옮겨다니는 장면이 떠올라서...
2. 그래서 머릿속에 그려진 꿈틀이의 컨셉을 제대로 잡고 방향을 정한 뒤 dfs를 돌리자
3. 나는 오른쪽 아래쪽 왼쪽 위쪽 순으로 꿈틀거리게끔 했다.
4. 코드는 아래에 있고, 나름 직관적이라 생각한다. 그냥 동남서북으로 dfs를 하나씩 재귀호출 했기 때문!
5. 근데 이렇게되면, 'ㅗ' 모양은 탐색하지 못한다. (머리가 목에 붙은채로 꿈틀대야하는데 머리가 떨어져서 배쪽으로 가는건 dfs는 지원하지 않는다 ㅋㅋ)
6. 이 부분은 따로 분기처리를 한다기보다, 일단 'ㅗ'를 제외한 모든 탐색을 마친 뒤, 이중포문을 하나 돌려서 탐색하기로 했다.

완전탐색에 좀 약한것같아서 완전탐색에 온 힘을 다하고있는데 그래도 문제가 풀리니까 재밌네 ㅋㅋ

재귀에 대한 감도 좀 잡은 것 같다.

코드

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

public class Main {
	static int[][] map;
	static boolean[][] visited;
	static int answer = 0;
	static int N, M;
	public static void init() 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 + 3][M + 3];
		visited = new boolean[N + 3][M + 3];
		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());
			}
		}		
	}
	public static void dfs(int x, int y, int depth, int sum) {
		if(depth == 4) 
		{	
			answer = Math.max(answer, sum);
			return ;
		}
		visited[x][y] = true;

		if(y < M && !visited[x][y + 1]) //오른쪽
		{
			dfs(x, y + 1, depth + 1, sum + map[x][y + 1]);
		}
		if(x < N && !visited[x + 1][y]) { //아래
			dfs(x + 1, y, depth + 1, sum + map[x + 1][y]);
		}
		if(x > 0 && !visited[x - 1][y]) { //왼쪽
			dfs(x - 1, y, depth + 1, sum + map[x - 1][y]);
		}
		if(y > 0 && !visited[x][y - 1]) { //위쪽..? 이건 굳이 해야하나?
			dfs(x, y - 1, depth + 1, sum + map[x][y - 1]);			
		}
		visited[x][y] = false;
	}
	public static int getMax(int a, int b, int c) {
		return a > b ? a > c ? a : c : b > c ? b : c ; 
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		init();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dfs(i, j, 0, 0);				
			}
		}
		int w, h, temp1 = 0, temp2 = 0, temp3 = 0, temp4 = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				w = map[i][j] + map[i][j + 1] + map[i][j + 2];
				h = map[i][j] + map[i + 1][j] + map[i + 2][j];
				temp1 = w + map[i + 1][j + 1]; // ㅜ
				temp2 = h + map[i + 1][j + 1]; // ㅏ
				
				answer = getMax(answer, temp1, temp2);
				if(i > 0) {
					temp3 = w + map[i - 1][j + 1]; //ㅗ
				}
				if(j > 0) {
					temp4 = h + map[i + 1][j - 1]; //ㅓ
				}
				answer = getMax(answer, temp3, temp4);
			}
		}
		System.out.print(answer);
	}
}