P14500. 테트로미노

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

14500번: 테트로미노

설명

처음 생각한 방법은 테트로미노를 만들 수 있는 경우의 수를 모두 계산하여 풀이하는 방법이다. 하지만 너무 복잡하다. 

 

이 문제는 테트로미노를 만들 수 있는 경우의 수를 두가지로 나누어 풀이할 수 있다.

1. ㅜ 모양이 아닌 경우 👉 dfs로 탐색한다.

2. ㅜ 모양인 경우 👉 직접 좌표를 계산하거나, 조합으로 풀이한다.

 

1. ㅜ 모양이 아닌 경우

• 노란 칸: 탐색 시작 칸
• 파란 칸: dfs로 탐색하는 칸

private static void dfs(int y, int x, int depth, int sum) {
	if (depth == 4) {
    	result = Math.max(result, sum);
        return;
     }
     
     for (int i = 0; i < 4; i++) {
     	int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(ny < 0 || nx >= N || nx < 0 || nx >= M) {
        	continue;
        }
        
        if (visit[ny][nx]) {
        	continue;
		}
        
        visit[ny][nx] = true;	// 방문 처리를 true로 한다.
        dfs(ny, nx, depth+1, sum+map[ny][nx]);
        visit[ny][nx] = false;	// dfs를 완료하고 다시 방문 처리를 false로 한다.
    }
}

dfs를 완료하고 다시 방문 처리를 false로 하는 이유는 이 다음에는 해당 지점이 시작 지점이 될 수 있기 때문이다. 

 

2. ㅜ 모양인 경우

가운데 중심에서 인접한 4칸 중 3칸을 선택한다. (조합을 이용한다!)

private static void combi(int y, int x, int depth, int start, int sum) {
	if (depth == 3) {	// 중심으로부터 선택한 파란색의 개수
    	result = Math.max(result, sum);
        return;
	}        
     
    for (int d = start; d < 4; d++) {
    	int ny = y + dy[d];
        int nx = x + dx[d];
        
        if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
        	continue;
		}            
         
        combi(y, x, depth + 1, d + 1, sum + map[ny][nx]);
	}        
}

combi 함수를 재귀 호출할 때, d+1을 사용하는 이유는 무엇일까?

for문에서 d는 방향을 나타내기 위해 사용된다. 

start 매개변수는 재귀 호출에서 시작 방향을 제어하는데 사용된다. 

combi 함수가 재귀적으로 호출될 때, depth 매개변수는 1증가하여 다음 재귀로 이동한다. 이때 시작 방향을 변경하기 위해 d+1이 사용된다. 

재귀 호출에서 start를 d+1로 설정하여, 실제로는 d 방향을 건너뛰고 다음 재귀 호출에서 다음 방향을 탐색하게 된다. 즉, 같은 조합 내에서 동일한 방향이 두 번 탐색되지 않도록 한다.

 

실제 작동 방식은 다음과 같다.

- d가 초기에 0(위)이면, 재귀 호출 시 start를 d+1로 설정하여 다음 방향(아래)를 재귀 호출에서 탐색한다. 

- 다음 반복에서 d가 1이면, 재귀 호출은 d+1로 설정되어 2가 된다. 

=> 이런 식의 반복이 계속된다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N, M, result = Integer.MIN_VALUE;
    static int[][] map;
    static boolean[][] visit;
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        map = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }

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

        sb.append(result);
        System.out.println(result);
    }

    private static void combi(int y, int x, int depth, int start, int sum) {
        if (depth == 3) {
            result = Math.max(result, sum);
            return;
        }

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

            if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
                continue;
            }

            combi(y, x, depth + 1, d + 1, sum + map[ny][nx]);
        }
    }

    private static void dfs(int y, int x, int depth, int sum) {
        if (depth == 4) {
            result = Math.max(result, sum);
            return;
        }

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

            if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
                continue;
            }

            if (visit[ny][nx]) {
                continue;
            }

            visit[ny][nx] = true;
            dfs(ny, nx, depth + 1, sum + map[ny][nx]);
            visit[ny][nx] = false;
        }
    }
}

 

Reference

https://developer-u.tistory.com/103