[Algorithm] SW 기출문제 - 테트로미노(14500) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 테트로미노 자바 풀이를 작성하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

 

1. 풀이 소스

 

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        board.run();
        
        System.out.println(board.getMaxSum());
    }
}

class Board{
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};
    
    int n; // 행의 개수
    int m; // 열의 개수
    int maxSum; // 최대 값
    int[][] map; // 각 행과 열에 해당하는 값을 저장할 2차원 배열
    boolean[][] visited; // 방문 여부
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void run() {
        
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                int count = 1; // 시작은 1로 설정
                int sum = map[row][col]; // 합 초기화

                visited[row][col] = true; // 맨 처음 선택하는 좌상단 좌표는 방문처리
                dfs(row, col, sum, count); // dfs 시작
                visited[row][col] = false; // dfs 종료 후 맨 처음 선택한 시작점 방문 해제
            }
        }
    }
    
    void dfs(int row, int col, int sum, int count) {
        
        if (count == 4) {
            maxSum = Math.max(maxSum, sum); // 최대 값 구하기
            return; // 재귀 종료
        }

        for (int i = 0; i < 4; i++) {
            int nextR = row + DR[i]; // 이동할 row  
            int nextC = col + DC[i]; // 이동할 col

            if (!isValid(nextR, nextC)) continue; // 유효한 범위가 아니거나 이미 방문한 경우

            if (count == 2) { // 만약 2라면 이전 행과 열에서 한 번 더 움직일 수 있도록 row, col로 연결 
                visited[nextR][nextC] = true;
                dfs(row, col, sum + map[nextR][nextC], count + 1);
                visited[nextR][nextC] = false;
            }

            visited[nextR][nextC] = true; // 방문 여부 표시
            dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
            visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시
        }
    }
    
    boolean isValid(int row, int col) { // 유효한 범위에 아직 방문하지 않은 경우 
        return row >= 0 && row < n && col >= 0 && col < m && !visited[row][col];
    }
    
    int getMaxSum() {
        return this.maxSum;
    }
    
}

 

 

2. 풀이 중점 사항

 

해당 문제는 DFS로 완전탐색을 진행하되 블록의 규칙을 찾을 수 있어야 했습니다.

 

***  *     *  ***   **  **   *    * 
*    *** ***    *    *  *    *    *
                     *  *    **  **

*    *  **    **  
**  **   **  **   
 *  *       

*    *   *  ***
**  **  ***  *
*    *


****

*
*
*
* 

**
**

 

해당 블록을 자세히 보면, 특정 점을 시작으로 마치 방문하지 않은 노드를 방문하는 것처럼 이뤄진 것을 확인할 수 있습니다.

예를 들어 아래의 블록들이 있다면 해당 블록은 x x x에서 파생된 것이라고 볼 수 있습니다.

 

x  x  x   |    x   x   x   x   |    x        

        x   |                       |    x  x  x   

 

이는 방문하지 않은 곳으로 노드를 옮겨가며 총 4번만 움직이면 ㅜ, ㅗ, ㅏ, ㅓ 를 제외한 블록은 모두 이동할 수 있음을 의미합니다.

 

ㅏ, ㅗ, ㅓ, ㅜ 는 다음의 방법으로 이동할 수 있습니다.

두번째 이동하는 장소에서  다음으로 이동할 때, nextR, nextC에 대한 map의 합을 구한 후, 경로를 row, col로 설정하는 것입니다.

   

 

 

 

 

    for (int i = 0; i < 4; i++) {
        int nextR = row + DR[i]; // 이동할 row  
        int nextC = col + DC[i]; // 이동할 col

        if (!isValid(nextR, nextC)) continue; // 유효한 범위가 아니거나 이미 방문한 경우

        if (count == 2) { // 만약 2라면 이전 행과 열에서 한 번 더 움직일 수 있도록 row, col로 연결 
            visited[nextR][nextC] = true;
            dfs(row, col, sum + map[nextR][nextC], count + 1);
            visited[nextR][nextC] = false;
        }

        visited[nextR][nextC] = true; // 방문 여부 표시
        dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
        visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시
    }

 

이 그림과 함께 해당 코드를 살펴보면, row, col을 다시 dfs의 재귀 위치로 설정함으로써, 4개를  방문한 후 maxSum 처리를 할 수 있습니다.

 

    visited[nextR][nextC] = true; // 방문 여부 표시
    dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
    visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시

 

다음과 같이 방문 처리 후 다시 방문을 푸는 재귀를 위해 이동한 4개의 움직임이 visited[row][col] = true로 계속 유지된다면
하나의 경로가 끝난 후 실행되는 다음 dfs에 영향을 줄 수 있습니다.

따라서,  count == 4가 된다면 maxSum을 업데이트하기 때문에 현재 방문 여부는 return; 이후 visited[row][col] = false로 처리함으로써 다시 리셋할 수 있게 됩니다.

 

 

이상으로 백준 테트로미노 자바 풀이를 마치도록 하겠습니다. 감사합니다.!