[Softeer] S540 garage game

[Softeer]

Question

Language: Python

해당 문제는 모든 경우의 수를 고려하면서 가장 최적의 결과를 찾는 Bruteforce 형태의 문제이면서 recursion을 통해 재귀적으로 접근하는 유형의 문제이다.

해당 문제에 요구되는 동작은 크게 2가지이다.

1. 인접한 차량에 대해 같은 색깔을 가지는 집단 구하기

def find_components(arr):
    visited=[[False]*n for _ in range(3*n)]

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    components=[]
    for start_row in range(2*n,3*n):
        for start_col in range(n):
            if visited[start_row][start_col]:
                continue
            visited[start_row][start_col]=True
            queue=deque([(start_row,start_col)])
            color=arr[start_row][start_col]
            min_row,min_col,max_row,max_col=start_row,start_col,start_row,start_col
            col_info=[[inf,0] for _ in range(n)]
            col_info[start_col]=[start_row,1]
            count=1
            while queue:
                row,col=queue.popleft()

                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    if next_row <2*n or next_row >= 3*n or next_col < 0 or next_col>=n:
                        continue
                    if visited[next_row][next_col]:
                        continue
                    if arr[next_row][next_col] != color:
                        continue
                    visited[next_row][next_col]=True

                    min_row=min(min_row,next_row)
                    min_col=min(min_col,next_col)
                    
                    max_row=max(max_row,next_row)
                    max_col=max(max_col,next_col)

                    col_info[next_col]=[min(col_info[next_col][0],next_row),col_info[next_col][1]+1]
                    count+=1
                    queue.append((next_row,next_col))
            components.append([(count + (max_row-min_row+1)*(max_col-min_col+1)),col_info])

    return components

인접한 좌표에 대해 같은 색깔을 가지는 차량끼리 묶는 과정은 bfs을 이용하여 component을 찾는 방식으로 해결할 수 있다. component을 찾는 과정으로 min_row,min_col,max_row,max_col을 찾아서 해당 구역을 포함하는 가장 작은 직사각형의 넓이를 빠르게 구할 수 있도록 한다. 또한, 각 column 별로 없앨 좌표점에 대한 정보(start_row, count)을 기록해서 나중에 차량을 아래로 이동시키는 작업을 수월케 만든다.

1. 차량 아래로 이동

def move_cars(arr,col_info):
    for col in range(n):
        start_row,count=col_info[col]

        #해당 열에 움직이는 칸이 없는 경우 
        if start_row==inf:
            continue
        
        #사라진 만큼 이동시킨다.
        for row in range(start_row-1,-1,-1):
            arr[row+count][col]=arr[row][col]

component을 구하는 과정에서 계산한 column 정보를 토대로 차량으로 아래로 이동시키는 작업을 진행한다.

Solution

import sys
from collections import deque
from math import inf

def find_components(arr):
    visited=[[False]*n for _ in range(3*n)]

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    components=[]
    for start_row in range(2*n,3*n):
        for start_col in range(n):
            if visited[start_row][start_col]:
                continue
            visited[start_row][start_col]=True
            queue=deque([(start_row,start_col)])
            color=arr[start_row][start_col]
            min_row,min_col,max_row,max_col=start_row,start_col,start_row,start_col
            col_info=[[inf,0] for _ in range(n)]
            col_info[start_col]=[start_row,1]
            count=1
            while queue:
                row,col=queue.popleft()

                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    if next_row <2*n or next_row >= 3*n or next_col < 0 or next_col>=n:
                        continue
                    if visited[next_row][next_col]:
                        continue
                    if arr[next_row][next_col] != color:
                        continue
                    visited[next_row][next_col]=True

                    min_row=min(min_row,next_row)
                    min_col=min(min_col,next_col)
                    
                    max_row=max(max_row,next_row)
                    max_col=max(max_col,next_col)

                    col_info[next_col]=[min(col_info[next_col][0],next_row),col_info[next_col][1]+1]
                    count+=1
                    queue.append((next_row,next_col))
            components.append([(count + (max_row-min_row+1)*(max_col-min_col+1)),col_info])

    return components


def move_cars(arr,col_info):
    for col in range(n):
        start_row,count=col_info[col]

        #해당 열에 움직이는 칸이 없는 경우 
        if start_row==inf:
            continue
        
        #사라진 만큼 이동시킨다.
        for row in range(start_row-1,-1,-1):
            arr[row+count][col]=arr[row][col]

def print_board(board):
    for row in board:
        print(*row)

def python_copy(src):
    array=[[0] * n for _ in range(3*n)]

    for row in range(3*n):
        for col in range(n):
            array[row][col]=src[row][col]
    
    return array


def solution(index,arr,result):
    global max_result
    if index==3:
        max_result=max(max_result,result)
        return

    components=find_components(arr)


    for component in components:
        temp_result,col_info=component
        temp_arr=python_copy(arr)

        move_cars(temp_arr,col_info)

        solution(index+1,temp_arr,result+temp_result)

    

if __name__ == "__main__":
    n=int(sys.stdin.readline())
    carmap=[list(map(int,sys.stdin.readline().split())) for _ in range(3*n)]
    max_result=0
    solution(0,carmap,0)
    print(max_result)