백준, 테트로미노(14500, java)

문제 설명

테트로미노 5개를 주어진 2차원 배열에 두었을 때 각 칸의 합의 최댓값을 구하는 문제이다. 이때 테트로미노는 회전하거나 대칭시켜도 된다.

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

문제 풀이

문제를 처음 봤을 때는 테트로미노로 만들 수 있는 모든 문양을 2차원 배열로 만든 다음에 주어진 지도에 대입시키려고 했다. 그러나 파란색과 노란색은 경우의 수가 적지만 주황색부터는 경우의 수가 너무 많아져서 분명 다른 풀이가 있을 거라는 생각이 들었다. 

 

그리고 실제로도 다른 풀이가 있었다.

 

깊이 우선 탐색으로 푸는 문제인데, 예상보다 더 간단해서 솔직히 좀 놀랐다.

 

아래처럼 3x4의 2차원 배열이 있다고 생각해보자.

x

그렇다면 x에서 시작해서 상하좌우로 총 3번 탐색하면 어떤 경우에도 테트로미노의 경우에 포함이 된다.

x	x	x	x

x	x	x
		x

x	x
	x	x

x	x
	x
	x

놀랍지 않는가? 실제로 주어진 테트로미노로 x 친 부분을 전부 만들 수 있다.

 

다만, 분홍색 테트로미노는 2번째 위치에서 총 2번 탐색을 해줘야 한다. 즉, 탐색이 뻗어나가는 것이 아니라 2번째 위치에서 한 번 탐색을 했다면 다시 2번째 위치로 돌아가 다른 방향으로 탐색을 해줘야 하는 의미이다. 그래서 해당 문제를 너비우선 탐색으로 풀지 못한다.

코드

java

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

public class Main {

    public static int r, c, answer;
    public static int[][] map;
    public static boolean[][] visit;
    public static int[] dR = {-1, 0, 1, 0}; //북동남서
    public static int[] dC = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        answer = 0;

        map = new int[r][c];
        visit = new boolean[r][c];


        for(int i=0; i<r; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<c; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                visit[i][j] = true;
                dfs(i, j, map[i][j], 1);
                visit[i][j] = false;
            }
        }

        System.out.println(answer);

    }

    public static void display(){
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(visit[i][j] == true){
                    System.out.print("t ");
                }else{
                    System.out.printf("f ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void dfs(int row, int col, int sum, int count){
        if(count == 4){
            //System.out.println(count);
            //display();
            answer = Math.max(answer, sum);
            return;
        }

        //System.out.println(count);
        //display();

        for(int i=0; i<4; i++){
            int nRow = row + dR[i];
            int nCol = col + dC[i];

            if(nRow >= 0 && nRow < r && nCol >= 0 && nCol < c){
                if(!visit[nRow][nCol]){
                    if(count == 2){
                        visit[nRow][nCol] = true;
                        dfs(row, col, sum+map[nRow][nCol], count+1);
                        visit[nRow][nCol] = false;
                    }

                    visit[nRow][nCol] = true;
                    dfs(nRow, nCol, sum+map[nRow][nCol], count+1);
                    visit[nRow][nCol] = false;
                }

            }
        }

    }


}