[Problems] [Gold V] 백준 테트로미노 문제풀이

문제 설명

문제 링크: https://www.acmicpc.net/problem/14500

소요시간: 50분

위와 같은 블록이 있을 때 정수가 적여있는 칸에 놓아 가장 큰 수를 구하는 것이다.

예를 들어,

블럭 하나를 사용하여 입력 숫자를 조합하여 가장 큰 수를 만드는 것이다.

해당 결과는 19가 가장 큰 값이다.

핵심 요구사항

1. Y, X 축 크기를 받는다.

2. 입력받은 크기만큼 정수를 받는다.

3. L, ㅣ, ㅁ, ㅗ 모양의 블럭을 탐색한다.

 

한붓그리기를 생각해보자.

L, ㅣ, ㅁ 모양은 한붓그리기가 가능한 모양이다.

ㅗ는 한번 돌아갔다가 그려야하기 때문에 이는 완전탐색으로 풀 수 없다.

ㅗ의 가운데를 중심으로 +를 구하고 가장 작은 값을 구한다.

+의 정수합 - 가장 작은 값을 뽑아내면 큰 값을 구할 수 있다.

 

풀이 코드

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

public class Main {

    static int[][] map;
    static boolean[][] visited;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int maxSum;

    static int N;
    static int M;

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

        map = new int[N][M];
        visited = new boolean[N][M];
        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());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true; // 'ㅗ'를 제외한 블록은 DFS로 탐색
                dfs(i, j, 1, map[i][j]);
                maxSum = Math.max(getLast(i, j), maxSum);
                visited[i][j] = false;
            }
        }
        System.out.println(maxSum);

    }

    static void dfs(int row, int col, int cnt, int sum) {
        if (cnt == 4) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        for (int i = 0; i < dirs.length; i++) {
            int newY = row + dirs[i][0];
            int newX = col + dirs[i][1];

            if (isRange(newY, newX) && !visited[newY][newX]) {
                visited[newY][newX] = true;
                dfs(newY, newX, cnt + 1, sum + map[newY][newX]);
                visited[newY][newX] = false;
            }
        }
    }

    static int getLast(int y, int x) {
        int base = map[y][x];
        int count = 0;// 사방 탐색 성공 회수
        int min = Integer.MAX_VALUE;

        // 중심점을 중심으로 사방 탐색
        for (int[] dir : dirs) {
            int newY = y + dir[0];
            int newX = x + dir[1];
            if (isRange(newY, newX) && x < M) {
                count++;
                base += map[newY][newX];
                min = Math.min(min, map[newY][newX]);
            }
        }
        // 4방 탐색이 4군데 다 성공했다면 최소값을 빼주기 - 이게 그나마 최대값
        if (count == 4) {
            return base - min;
        }
        // 3 방향만 성공했으면 그대로 진행
        else if (count == 3) {
            return base;
        }
        // 나머지경우는 모양 만들기 실패
        else {
            return -1;
        }
    }

    private static boolean isRange(int nr, int nc) {
        return 0 <= nr && nr < N && 0 <= nc && nc < M;
    }

}

개선점

이전에 DFS 문제를 풀었을 때는 visited 배열을 생략하면서 구현했었다.

이 문제도 visited 배열을 생략해보자.

배열 범위 에러로 return 0 <= nr && nr < N && 0 <= nc && nc < M;

위 코드를 추가했다. (맵에 벗어나는지 확인하는 코드)

사실 이 코드는 맵의 크기를 늘리고, 여유롭게 생성하면 필요없는 코드다...

 

1.visited 변수 제거

2. 0 <= nr && nr < N && 0 <= nc && nc < M로 확인하지 않고 map 자체가 벗어나지 않도록 크게 지을 것

 

느낀점

완전 탐색이라는 풀이를 생각하지 않았더라면, 풀지 못했을 것 같다.