[백준 14500] 테트로미노 / 자바 / DFS + 구현

문제         

레벨: G4
알고리즘: DFS + 구현 
풀이시간: 1시간 
힌트 참조 유무: 유 

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

1 번째 시도   

[알고리즘 설명]

 

4방향 depth 4로 dfs를 해보면 'ㅜ' 모양 빼고 다 만들 수 있다.

'ㅜ' 모양을 만들려면 depth가 2일 때, 즉 'ㅜ'의 중앙일 때 그 위치에서 next로 넘어가지 않고, next의 값만 +해서 파라미터에 넘겨줘 재귀를 한다. 그렇다면 dpeth는 3이 됐는데 전이랑 위치가 변함이 없고 next의 값은 반영 되어있다. 실질적으로 한 칸 갔다 온 걸로 치는 것이다.

 

dfs 구현은 꾸준히 연습해야겠다.

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

public class Main {

	static int max = Integer.MIN_VALUE;
	static int[][] arr;
	static boolean[][] visit;
	static int n;
	static int m;

	// 상하좌우
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};

	public static void main(String[] args) throws NumberFormatException, 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());
		arr = new int[n][m];
		visit = new boolean[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());
			}
		}

		// 전체 탐색 (dfs)
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				visit[i][j] = true;
				solve(i,j,arr[i][j],1);
				visit[i][j] = false;
			}
		}

		System.out.println(max);
	}

	static void solve(int row, int col, int sum, int count) {

		// 테트로미노 완성 시 수들의 합 계산
		if(count == 4) {
			max = Math.max(max, sum);
			return;
		}

		// 상하좌우 탐색
		for(int i = 0; i < 4; i++) {
			int curRow = row + dx[i];
			int curCol = col + dy[i];

			// 범위 벗어나면 예외 처리
			if(curRow < 0 || curRow >= n || curCol < 0 || curCol >= m) {
				continue;
			}

			// 아직 방문하지 않은 곳이라면
			if(!visit[curRow][curCol]) {

				// 보라색(ㅗ) 테트로미노 만들기 위해 2번째 칸에서 탐색 한번 더 진행
				if(count == 2) {
					visit[curRow][curCol] = true;
					solve(row, col, sum + arr[curRow][curCol], count + 1);
					visit[curRow][curCol] = false;
				}

				visit[curRow][curCol] = true;
				solve(curRow, curCol, sum + arr[curRow][curCol], count + 1);
				visit[curRow][curCol] = false;
			}
		}
	}
}