[BOJ] 14500 - 테트로미노 (Java)

알고리즘

• 구현
• 브루트포스 알고리즘

1. 문제

• 주어진 행렬에서 테트로미노 모양을 만들어 얻을 수 있는 최대 합을 구하는 문제
  

2. Idea

• 상하좌우를 완전 탐색하여 ㅜ 모양을 제외하고 모두 만들어낼 수 있다.
• ㅜ 모양은 탐색의 2번째 칸에서 양쪽으로 하나씩 움직여야 만들 수 있는 형태이기 때문에 상하좌우 탐색으로는 결과를 구할 수 없다.
  • 따라서, 탐색 시 2번째 칸 일때 3번째 탐색을 시작하는 위치를 3번째 탐색 위치로 하는 것이 아니라 2번째 칸에서 다시 한번 탐색하도록 하는 경우를 추가해주면 구할 수 있다.

3. 풀이

3.1. 변수 선언 및 초기화

n: 행렬의 가로 크기
m: 행렬의 세로 크기

• arr 배열에 행렬의 값을 저장
• visit 배열: 방문 처리를 위한 배열

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());
	}
}

3.2. solve 메소드 - DFS 탐색

solve 메소드

• DFS를 통해 테트로미노를 만들면서 각 경우의 최대 합 return
• 각 좌표를 방문하면서 해당 좌표에서 출발하는 테트로미노를 생성
• 테트로미노가 완성되면 그 때의 합을 최대 합과 비교하여 갱신
• DFS 탐색을 통해 4개의 칸을 방문한 경우, 최대 합을 갱신하고 종료

상하좌우 탐색

• 현재 위치에서 상하좌우로 이동하면서 아직 방문하지 않은 경우에 대해 DFS를 호출
• 범위를 벗어나거나 이미 방문한 경우는 제외하고 탐색

보라색(ㅜ) 테트로미노 예외 처리

• 보라색 테트로미노는 2번째 칸에서 탐색을 한 번 더 진행
• 이 경우를 처리하기 위해 count가 2일 때, 현재 위치에서 한 번 더 DFS를 호출

	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;
            }
        }
    }

3.3. 전체 좌표에 대한 DFS 탐색

• 이중 반복문을 통해 모든 좌표에 대해 DFS 탐색 시작
• 각 좌표에서 DFS를 호출하면서 최대 합을 찾아낸다.

// 전체 탐색 (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;
	}
}

3.4. 결과 출력

• 최종적으로 얻은 최대 합을 출력합니다.

System.out.println(max);

4. 전체코드

import java.io.*;
import java.util.*;

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;
            }
        }
    }
}