📃 문제

소프티어 - Garage game

📝 풀이

이 문제는 Python으로 하면 시간초과가 나와 풀지 못했다.
하지만 같은 로직으로 Java를 사용하니 통과했다...
이 이상의 최적화 방법이 떠오르지 않는데 혹시나 방법이 보이시면 댓글 부탁드려요.😂😂

고려사항

• 한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같다면 모두 사라진다. -> 하나의 자동차만 사라질 수 있다.
• 차고에서 자동차가 사라질 수 있는 경우는 존재하는 차량의 색상 갯수만큼 존재한다.
  이 모든 경우를 탐색하며 최고 점수를 구해야 한다.

Python 코드

import sys
input = sys.stdin.readline


def copy_box(now_box, box, b, l, r):
    for j in range(l, r + 1):
        for i in range(b, N):
            now_box[i][j] = box[i][j]


def copy_pointers(now_pointers, l, r):
    for i in range(l, r + 1):
        pointers[i] = now_pointers[i]


def init_box(box, b, l, r):
    """
    차고에 빈 자리가 있으면 아래로 채운 뒤 남은 자리는 위에서 떨어지는 자동차로 채운다.
    
    :param box: 차고
    :param b: bottom 
    :param l: left
    :param r: right
    :return: 
    """
    for j in range(l, r + 1):
        pointer = pointers[j]
        for si in range(b, N):
            i = si
            if box[i][j] == -1:
                flag = True
                while i < N:    # 빈 자리가 있으면 아래로 채우기
                    if box[i][j] != -1:
                        box[si][j] = box[i][j]
                        box[i][j] = -1
                        flag = False
                        break
                    i += 1
                if flag:
                    # 위에서 떨어지는 자동차로 채우기
                    box[si][j] = arr[pointer][j]
                    pointer += 1
        pointers[j] = pointer   # 다음에 떨어질 자동차 위칫값


def bfs(sx, sy, visited, box):
    """
    :param sx:
    :param sy:
    :param visited:
    :param box:
    :return: box[sx][sy]를 선택했을 때 얻을 수 있는 점수,
            사라진 자동차들을 포함하는 가장 작은 직사각형 범위 b, l, r
    """
    stack = [(sx, sy)]
    visited[sx][sy] = True
    color = box[sx][sy]
    cnt = 1

    min_x = min_y = 16
    max_x = max_y = 0
    while stack:
        x, y = stack.pop()
        box[x][y] = -1
        min_x = min(min_x, x)
        max_x = max(max_x, x)
        min_y = min(min_y, y)
        max_y = max(max_y, y)
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 > nx or nx >= N or 0 > ny or ny >= N:  continue
            if color != box[nx][ny]:    continue
            if visited[nx][ny]:          continue
            stack.append((nx, ny))
            visited[nx][ny] = True
            cnt += 1

    return cnt + (max_x - min_x + 1) * (max_y - min_y + 1), min_x, min_y, max_y


def simulation(box, score, round, b, l, r):
    """
    :param box: 차고
    :param score: 회차의 점수
    :param round: 회차
    :param b: bottom
    :param l: left
    :param r: right
    :return:
    """
    global max_score, pointers

    if max_score < score:
        max_score = score

    if round == 4:
        return

    init_box(box, b, l, r)

    now_box = [box[i][:] for i in range(N)]
    now_pointers = pointers[:]

    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j]:   continue
            plus, b, l, r = bfs(i, j, visited, now_box)

            simulation(now_box, score + plus, round + 1, b, l, r)

            copy_pointers(now_pointers, l, r)
            copy_box(now_box, box, b, l, r)


N = int(input())
M = 3 * N
temp = [list(map(int, input().split())) for _ in range(M)]
arr = [[] for _ in range(M)]    # 3번의 시뮬레이션에서 나올 수 있는 자동차들
for i in range(M - 1, -1, -1):
    arr[M - 1 - i] = temp[i]

pointers = [0] * N                  # 위에서 떨어질 차량을 가리키는 위칫값
box = [[-1] * N for _ in range(N)]  # 차고
max_score = 0

simulation(box, 0, 1, 0, 0, N-1)

print(max_score)

이 코드는 b20, b21에서 시간초과가 발생한다...

Java 코드

Python으로는 도저히 최적화 방법이 떠오르지 않아 Java를 사용해보았다.

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

public class Main {
	
    static int N;
    static int[][] arr;
    static int[] pointers;
    static int answer;
    static int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = 3 * N;
        arr = new int[M][N];
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                arr[M-1-i][j] = Integer.parseInt(st.nextToken());
            }
        }

        pointers = new int[N];			// 위에서 떨어질 차량을 가리키는 위칫값
        int[][] box = new int[N][N];	// 차고
        answer = 0;

        simulation(box, 0, 1, 0, 0, N - 1);

        System.out.println(answer);
    }

    /**
     * @param box 차고
     * @param score 회차의 점수
     * @param round 회차
     * @param b bottom
     * @param l left
     * @param r right
     */
    static void simulation(int[][] box, int score, int round, int b, int l, int r) {
    	if (answer < score) {
    		answer = score;
    	}

        if (round == 4)
            return;

        initBox(box, b, l, r);
        int[][] nowBox = new int[N][N];
        for (int i = 0; i < N; i++) {
            nowBox[i] = Arrays.copyOf(box[i], N);
        }
        int[] savedPointers = Arrays.copyOf(pointers, N);

        boolean[][] visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j])
                    continue;
                int[] res = bfs(i, j, visited, nowBox);
                int plus = res[0];
                b = res[1];
                l = res[2];
                r = res[3];
                simulation(nowBox, score + plus, round + 1, b, l, r);
                copyPointers(savedPointers, l, r);
                copyBox(nowBox, box, b, l, r);
            }
        }
    }
  
    /**
     * 
     * @param sx
     * @param sy
     * @param visited
     * @param box
     * @return box[sx][sy]를 선택했을 때 얻을 수 있는 점수,
            사라진 자동차들을 포함하는 가장 작은 직사각형 범위 b, l, r
     */
    static int[] bfs(int sx, int sy, boolean[][] visited, int[][] box) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{sx, sy});
        visited[sx][sy] = true;
        int color = box[sx][sy];
        int cnt = 1;

        int minX = 16, minY = 16, maxX = 0, maxY = 0;
        while (!stack.isEmpty()) {
            int[] pos = stack.pop();
            int x = pos[0], y = pos[1];
            box[x][y] = 0;
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N || color != box[nx][ny] || visited[nx][ny])
                    continue;
                stack.push(new int[]{nx, ny});
                visited[nx][ny] = true;
                cnt++;
            }
        }

        return new int[] {cnt + (maxX - minX + 1) * (maxY - minY + 1), minX, minY, maxY};
    }
  
    /**
     * 차고에 빈 자리가 있으면 아래로 채운 뒤 남은 자리는 위에서 떨어지는 자동차로 채운다.
     * 
     * @param box 차고
     * @param b bottom
     * @param l left
     * @param r right
     */
    static void initBox(int[][] box, int b, int l, int r) {
        for (int j = l; j <= r; j++) {
            int pointer = pointers[j];
            for (int si = b; si < N; si++) {
                int i = si;
                if (box[i][j] == 0) {
                    boolean flag = true;
                    while (i < N) {	// 빈 자리가 있으면 아래로 채우기
                        if (box[i][j] != 0) {
                            box[si][j] = box[i][j];
                            box[i][j] = 0;
                            flag = false;
                            break;
                        }
                        i++;
                    }
                    if (flag) {	// 위에서 떨어지는 자동차로 채우기
                        box[si][j] = arr[pointer][j];
                        pointer++;
                    }
                }
            }
            pointers[j] = pointer;
        }
    }
    
    static void copyPointers(int[] savedPointers, int l, int r) {
        for (int i = l; i <= r; i++) {
            pointers[i] = savedPointers[i];
        }
    }
  
    static void copyBox(int[][] nowBox, int[][] box, int b, int l, int r) {
        for (int j = l; j <= r; j++) {
            for (int i = b; i < N; i++) {
                nowBox[i][j] = box[i][j];
            }
        }
    }
}

통과 871ms, 58.15MB