완전 탐색으로 하기엔 너무 좌표 계산이 번거롭고 실수할 가능성도 높아서 시간이 오래 걸리겠다는 느낌이 들었다. 그렇다면?

테트로미노 문제 바로가기

문제 분석

1. 연결된 노드인가 (yes) → 그래프
2. 이웃을 기준으로 탐색하고 깊이가 정해져 있는가 (yes) → DFS / BFS
3. 정해진 최대 깊이까지 탐색인가 (yes) → DFS

접근법

한 점에서 상하좌우로 총 4개의 점을 방문하면 그 도형은 항상 테트로미노다.
단 ㅜ,ㅗ,ㅏ,ㅓ 모양은 연결된 노드 탐색중 가운데 기준점을 재방문하므로 이전에 방문한 노드는 다시 탐색하지 않는 dfs를 적용할 수 없다. 그래서 따로 처리한다. 그리고 대칭, 회전해도 ㅜ,ㅗ,ㅏ,ㅓ 모양 밖에 없다.

정답 코드

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

public class Main {
    static int[] dx = new int[] {-1, 1, 0, 0};
    static int[] dy = new int[] {0, 0, -1, 1};
    static int[][][] pink = new int[][][] {
        {{0,-1},{0,0},{0,1},{1,0}},  // ㅜ
        {{0,-1},{0,0},{-1,0},{1,0}}, // ㅓ
        {{0,-1},{0,0},{-1,0},{0,1}}, // ㅗ
        {{-1,0},{0,0},{1,0},{0,1}}   // ㅏ
    };
    static int[][] map;
    static boolean[][] visit;
    static int n, m, answer;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visit = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        
        for(int r = 0; r < n; r++) {
            for(int c = 0; c < m; c++) {
                visit[r][c] = true;
                findMaxTetromino(r, c, 1, map[r][c]);
                visit[r][c] = false;
                findPink(r, c);
            }
        }
        
        System.out.print(answer);
        sc.close();
    }
    
    // 파랑, 주황, 초록, 노랑
    static void findMaxTetromino(int r, int c, int cnt, int sum) {
        if(cnt == 4) {
            answer = Math.max(answer, sum);
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            
            if(!(nr>=0 && nr<n && nc>=0 && nc<m)) continue;
            if(visit[nr][nc]) continue;
            
            visit[nr][nc] = true;
            findMaxTetromino(nr, nc, cnt+1, sum+map[nr][nc]);
            visit[nr][nc] = false;
        }
    }
    
    // 핑크
    static void findPink(int r, int c) {
        for(int i = 0; i < 4; i++) {
            int[][] list = pink[i];
            int sum = 0;
            
            for(int j = 0; j < 4; j++) {
                int nr = r + list[j][0];
                int nc = c + list[j][1];
                
                if(!(nr>=0 && nr<n && nc>=0 && nc<m)) break;
                
                sum += map[nr][nc];
                if(j == 3) answer = Math.max(answer, sum);
            }
        }
    }
}

시간 복잡도

findMaxTetromino: O(n × m)
findPink: O(n × m × 4)
따라서 두 시간 복잡도의 합은 최종적으로 O(n×m) 이다.