[BOJ] 14391번 종이 조각 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

DFS 풀이

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

public class Main {
    static int N, M, max;
    static char[][] map;
    static boolean[][] used;

    public static void main(String[] args) 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());
        max = Integer.MIN_VALUE;
        map = new char[N][M];
        used = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        dfs(0,0);
        System.out.println(max);
    }

    private static void dfs(int row, int col) {
        // 선택 완료 -> 최댓값 갱신
        if (row == N) {
            updateMax();
            return;
        }
        // 다음행으로 이동
        if (col == M) {
            dfs(row+1, 0);
            return;
        }
        // 가로, 세로 선택 가지 뻗기
        used[row][col] = true;
        dfs(row, col+1);
        used[row][col] = false;
        dfs(row, col+1);
    }

    private static void updateMax() {
        int sum = getSum();
        max = Math.max(max, sum);
    }

    private static int getSum() {
        int sum = 0;
        // 가로 계산
        sum = getRowSum(sum);
        // 세로 숫자 계산
        sum = getColSum(sum);
        return sum;
    }

    private static int getColSum(int sum) {
        for (int i = 0; i < N; i++) {
            int temp = 0;
            for (int j = 0; j < M; j++) {
                if (!used[i][j]) {
                    temp *= 10;
                    temp += map[i][j] - '0';
                } else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        return sum;
    }

    private static int getRowSum(int sum) {
        for (int i = 0; i < M; i++) {
            int temp = 0;
            for (int j = 0; j < N; j++) {
                if (used[j][i]) {
                    temp *= 10;
                    temp += map[j][i] - '0';
                } else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        return sum;
    }
}

비트마스킹 풀이

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

public class Main {
    static int N, M, max;
    static int[][] map;

    public static void main(String[] args) 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());
        max = Integer.MIN_VALUE;
        map = new int[N][M];
        init(br);
        bitmask();
        print();
    }

    private static void init(BufferedReader br) throws IOException {
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
    }

    private static void bitmask() {
        for(int s=0; s<(1<<(N*M)); s++) {
            int sum = 0;
            /* 가로(0) 찾기 */
            sum = getRowSum(s, sum);
            /* 세로(1) 찾기 */
            sum = getColSum(s, sum);
            /* 최댓값 갱신 */
            updateMax(sum);
        }
    }

    private static int getColSum(int s, int sum) {
        for(int j=0; j<M; j++) {
            int cur = 0;
            for(int i=0; i<N; i++) {
                int k = i*M +j;
                if( (s &(1<<k)) != 0) {    // s의 k번째 비트가 1이면-> 해당 숫자는 세로
                    cur *= 10;
                    cur += map[i][j];
                }else {    // 해당 숫자는 가로
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        return sum;
    }

    private static int getRowSum(int s, int sum) {
        for(int i=0; i<N; i++) {
            int cur = 0;
            for(int j=0; j<M; j++) {
                int k = i*M+j;
                if( (s &(1<<k)) ==0 ) {    // s의 k번째 비트가 0이면-> 해당 숫자는 가로
                    cur*= 10;
                    cur += map[i][j];
                }else {    // 해당 숫자는 세로
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        return sum;
    }

    private static void updateMax(int sum) {
        max = Math.max(max, sum);
    }

    private static void print() {
        System.out.println(max);
    }
}

📄 해설

• 재귀적으로 각 칸에 대해 가로, 세로 체크를 하고, 모든 맵을 탐색한 경우 합을 계산하고 최댓값을 갱신하면 되는 문제
• 비트마스킹으로도 풀 수 있는데, 작성자는 재귀를 이용하여 해결하였음
  • 효율 차이가 있나하고 둘 다 확인해봤는데, 차이가 없었음
• 재귀 과정
  1. 가로는 true, 세로는 false 로 방문 배열을 체크함
  2. 해당 열을 모드 체크한 경우 다음 행을 재귀 호출
  3. 모든 행의 체크가 완료된 경우 합을 구하고(getSum 메소드), 최댓값을 갱신함(updateMax 메소드)
     • 합은 가로로 선택된 수의 합, 세로로 선택된 수의 합을 각각 구해주어 계산 -> getColSum, getRowSum 메소드
• 가장 중요한 결과 도출 부분인 가로 세로의 합을 따로 구해주는 과정을 제대로 구현하지 못하여, 다른 코드들을 참고하였음
• 작성자가 아직 비스마스킹 공부를 시작한지 얼마 안돼서 능숙하지 못하여, 비트마스킹 풀이는 아래 글을 참고하였음
  비트마스킹 참조 글