백준 14500번. 테트로미노 (Java, Python)

Problem

• 문제 링크

종이 위에 테트로미노 블록을 하나 놓아서 각 칸에 놓인 숫자 합의 최대값을 구하는 문제입니다.

Solution

테트로미노 블록에 들어있는 모든 숫자를 더한 값 중 최대값을 찾는 문제입니다.

DFS 로 깊이 4 까지 탐색하면 간단하게 풀 수 있습니다.

대신 블록 중에 ㅗ 모양은 DFS 돌려도 나오지 않으므로 따로 예외처리를 해주시면 됩니다.

1. 맵의 꼭지점일 때
2. 맵의 테두리일때
3. 일반적일 때

이렇게 세 가지 경우로 나누어서 각각 하드코딩 해주었습니다.

Java Code

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

class Main {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int max = 0;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        m = stoi(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] = stoi(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                dfs(i, j, 0, 0);
                visited[i][j] = false;
                another(i, j);
            }
        }

        System.out.println(max);
    }

    // dfs로 깊이가 최대 4인 경우가 테트로미노, 단 ㅗ 모양은 없음
    static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (visited[nx][ny] != true) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, depth + 1, sum + map[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }

    // ㅗ 모양을 찾는다. 가운데 있는 좌표를 기준으로 세 방향을 탐색한다.
    static void another(int x, int y) {
        // 1. 맵의 꼭지점일때는 ㅗ 모양 불가능
        if ((x == 0 || x == n - 1) && (y == 0 || y == m - 1)) return;

        int sum = map[x][y];

        // 2. 맵의 테두리일때는 모양이 하나
        if (x == 0)
            sum += map[x][y - 1] + map[x][y + 1] + map[x + 1][y];
        else if (x == n - 1)
            sum += map[x][y - 1] + map[x][y + 1] + map[x - 1][y];
        else if (y == 0)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y + 1];
        else if (y == m - 1)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y - 1];
        else {
        // 3. 맵의 테두리가 아닐 때는 4 개의 모양을 비교
            sum = Math.max(sum, map[x][y] + map[x + 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x - 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x][y + 1] + map[x - 1][y] + map[x + 1][y]);
            sum = Math.max(sum, map[x][y] + map[x][y - 1] + map[x - 1][y] + map[x + 1][y]);
        }

        max = Math.max(max, sum);
    }
}

Python Code

# -*- coding: utf-8 -*-
 
import sys
 
n = m = 0
arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
maxVal = 0
 
## 최대 4개짜리 dfs로 전부 탐색하면됨
def dfs(x, y, visited, count, sumVal):
    global maxVal
 
    if count == 4:
        if maxVal < sumVal:
            maxVal = sumVal
        return
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
 
        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if visited[nx][ny] == False:
                visited[nx][ny] = True
                dfs(nx, ny, visited, count + 1, sumVal + arr[nx][ny])
                visited[nx][ny] = False
        
## ㅗ 모양은 dfs로 탐색이 안돼서 따로 처리해줌
## 가운데일 때를 기준으로 네방향 탐색
def fuck(x, y):
    global maxVal
    sumVal = arr[x][y]
    
    ## x, y가 모서리면 ㅗ 모양은 아예 불가능
    if x == 0:
        if y == 0 or y == m-1:
            return
    elif x == n-1:
        if y == 0 or y == m-1:
            return
 
    ## x나 y가 가장자리에 있으면 ㅗ 모양은 하나밖에 안나옴
    if x == 0:
        sumVal += arr[x+1][y] + arr[x][y-1] + arr[x][y+1]
    elif x == n-1: 
        sumVal += arr[x-1][y] + arr[x][y-1] + arr[x][y+1]    
    elif y == 0:
        sumVal += arr[x][y+1] + arr[x-1][y] + arr[x+1][y]    
    elif y == m-1:
        sumVal += arr[x][y-1] + arr[x-1][y] + arr[x+1][y]
    else:  
        sumlist = []
        sumlist.append(sumVal + arr[x+1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x-1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x][y+1] + arr[x-1][y] + arr[x+1][y])
        sumlist.append(sumVal + arr[x][y-1] + arr[x-1][y] + arr[x+1][y])
        sumVal = max(sumlist)
    
    if maxVal < sumVal:
        maxVal = sumVal
 
def solve():
    visited = [[False]*m for i in range(n)]
 
    for i in range(n):
        for j in range(m):
            fuck(i, j)
            visited[i][j] = True
            dfs(i, j, visited, 1, arr[i][j])
            visited[i][j] = False
 
 
if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
 
    for i in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
        
    solve()
    print(maxVal)