문제

BOJ 14500: 테트로미노 https://www.acmicpc.net/problem/14500

풀이

조건

• 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합의 최댓값을 구한다.

풀이 순서

• 'ㅗ' 모양을 제외한 나머지 4개의 모양은 DFS를 이용하여 구현할 수 있다.
• ㅗ 모양은 아래 코드의 주석을 통해 보는 것이 쉽다.
  • 탐색하는 기준은 가장 왼쪽, 왼쪽 중 가장 윗 쪽을 기준으로 한다.

코드

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

public class Main {
    
	static int N, M;
	static int[][] map;
	
	static int max = -1;
	
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static boolean[][] isVisited;
	
    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];
    	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());
    		}
    	}
    	
    	isVisited = new boolean[N][M];
    	
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<M; j++) {
    			// ㅗ 외의 4개 모양을 찾음
    			isVisited[i][j] = true;
    			bt(i, j, 1, map[i][j]);
    			isVisited[i][j] = false;
    			
    			// ㅗ 모양 찾음
    			oh(i, j);
    		}
    	}
    	
    	System.out.println(max);
	
    }
    
    // ㅗ 모양 외의 4개 모양
    static void bt(int x, int y, int length, int sum) {
    	// 4칸까지 모두 찾았으면 종료
    	if(length == 4) {
    		max = Math.max(sum, max);
    		return;
    	}
    	// DFS로 찾아나감
    	for(int t=0; t<4; t++) {
    		int nx = x + dx[t];
    		int ny = y + dy[t];
    		
    		if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
    		
    		if(!isVisited[nx][ny]) {
    			isVisited[nx][ny] = true;
        		
        		bt(nx, ny, length + 1, sum + map[nx][ny]);
        		
        		isVisited[nx][ny] = false;
        	}
    		
    	}
    	
    }
    
    // ㅗ 모양
    static void oh(int x, int y) {
    	int sum = 0;
    	
    	// ㅜ
    	if(x >= 0 && x+1 < N && y >= 0 && y+2 < M) {
    		sum = map[x][y] + map[x][y+1] + map[x][y+2] + map[x+1][y+1];
    		max = Math.max(sum, max);
    	}
    	
    	// ㅏ
    	if(x >= 0 && x+2 < N && y >= 0 && y+1 < M) {
    		sum = map[x][y] + map[x+1][y] + map[x+2][y] + map[x+1][y+1];
    		max = Math.max(sum, max);
    	}
    	
    	// ㅗ
    	if(x-1 >= 0 && x < N && y >= 0 && y+2 < M) {
    		sum = map[x][y] + map[x][y+1] + map[x][y+2] + map[x-1][y+1];
    		max = Math.max(sum, max);
    	}
    	
    	// ㅓ
    	if(x-1 >= 0 && x+1 < N && y >= 0 && y+1 < M) {
    		sum = map[x][y] + map[x][y+1] + map[x-1][y+1] + map[x+1][y+1];
    		max = Math.max(sum, max);
    	}
    }

}

정리

• 테트로미노 5종류를 모두 사용하는 것으로 잘못 이해하여 시간이 오래 걸렸다.