[Softeer] HSAT 2회 기출 - Garage game

문제

<문제와 관련없는 배경 설명>

자율주행 기술의 발전과 함께 차량 내 인포테인먼트 기술 또한 많은 주목을 받고 있다. 최근 자동차 실내에는 디스플레이의 대형화를 비롯해 새로운 제어 기술이 빠르게 적용되고 있는데, 완전 자율주행 시대가 다가올 수록 이런 변화가 가속화될 전망이다. 개인 맞춤형 인포테인먼트 시스템 역시 핵심 기능 중 하나다. 자율주행 시대에 발맞춰 차량 내 디지털 시스템을 활용한 게임을 개발하고 있다.

<문제설명>

게임의 룰은 가로 세로 $N$칸의 차고(격자)가 있고, 각 차고에는 색깔이 있는 자동차가 하나씩 있다.

한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같다면 모두 사라진다.

그리고 사라진 칸들과 연결된 칸들의 상하좌우 칸에 들어있는 자동차의 색이 같다면 함께 사라진다. (문제 하단 예시 참고.)

 

이때, 획득할 수 있는 점수는 사라진 자동차의 개수와 사라지는 차고 칸을 모두 포함하는 가장 작은 직사각형의 넓이의 합이다.

자동차들이 사라지고 나면 위에 있는 자동차들이 아래로 떨어져 빈 칸을 채운다.

위쪽에는 충분한 자동차들이 더 있어서 위에서 추가적으로 떨어지며 모든 칸을 채운다.

 

위에서 어떤 자동차들이 떨어질지는 입력으로 주어진다.

위와 같은 게임을 3차례 반복 했을 때, 주어진 조건에서 얻을 수 있는 가장 큰 점수를 계산하라.

 

<입력>

 

<출력>

주어진 조건에서 게임을 3차례 시뮬레이션 했을 때 얻을 수 있는 가장 큰 점수를 출력한다.

 

<예시>

위 예시에 대한 동작 예시이다.

첫 단계에서 사라지는 차의 개수는 6, 최소 직사각형 크기는 6이다.

두번째 단계에서 사라지는 차의 개수는 3, 최소 직사각형 크기는 3이다.

세번째 단계에서 사라지는 차의 개수는 9, 최소 직사각형 크기는 9이다.

따라서 위 값들을 모두 더하면 36이 얻을 수 있는 점수의 최댓갑이다.

---

풀이

예시를 따라가보면 이 문제는 이해가 어렵지 않다는 것을 느낄 것이다.

이해가 쉽다고 문제 풀이가 꼭 쉬운 것은 아니지만 문제부터 이해가 가지 않는 문제보단 나은 것 같다.

 

먼저 입력을 받고 시뮬레이션 한 후 값을 가져오는 흐름으로 코드를 구성했다.

garage는 3차원의 리스트로 garage[0]~garage[2]은 각각 2차원 리스트로 1단계~3단계 상황을 나타낸다.

reverse를 통해 나중에 들어온 입력이 차고에서 낮은 위치에 있게끔 하도록 처리했다.

largest는 최고 점수를 기록할 변수이다.

n = int(input())
garage = [[[] for _ in range(n)] for _ in range(3)] #총 3차원 리스트
for _ in range(3*n):
    temp = list(map(int,input().split()))
    for i in range(n):
        garage[0][i].append(temp[i])

for i in range(n):
    garage[0][i].reverse()

largest = 0
simulate(0,0) #현재라운드, 현재까지 점수 합
print(largest)

 

이제 simulate함수를 보자.

for x, y를 통해 모든 칸을 순회한다.

해당 칸의 visit이 false여서 아직 방문되지 않은 칸에 대해 dfs를 수행한다,.

만약 마지막 단계라면 여태까지 시뮬레이션 했던 결과가 역대 최고 점수보다 큰지를 비교하고 최고 점수를 갱신한다.

마지막 단계가 아니면 remove()를 통해 찾은 그룹을 0으로 지우고 다음 단계의 초기 상태를 만든다.

이후 refill()을 통해 빈 공간에 차를 떨어뜨린다.

이제 다음단계를 시뮬레이션한다.

 

neighbor은 해당칸과 색이 같아 같은 그룹으로 묶이는 차고 좌표를 모은 것이다.

count는 이 좌표들의 개수이다.

def simulate(rnd, total):
    global largest
    visit = [[False for _ in range(n)] for _ in range(n)]
    hasNeighbor = calculateNeighbor(rnd)

    for x in range(n):
        for y in range(n):
            if visit[x][y]:
                continue

            left = right = x
            bottom = top = y
            count = 0


            if rnd ==2 and hasNeighbor[x][y] == 0:
                count, area = 1,1
                visit[x][y] = True
            else:
                neighbor = []
                count, left, right, bottom, top, neighbor = dfs(rnd, count, x, y, visit, left, right, bottom, top, neighbor)
                area = (right-left+1)*(bottom-top+1)
            newTotal = total + area
            
            if rnd == 2:
                if newTotal > largest:
                    largest = newTotal
            else:
                remove(rnd, neighbor)
                refill(rnd)
                simulate(rnd+1, newTotal)

def remove(rnd, neighbor): #다음 라운드를 위해
    garage[rnd+1] = [item[:] for item in garage[rnd]] #깊은 복사
    for cell in neighbor:
        x,y = cell[0], cell[1]
        garage[rnd+1][x][y] = 0

def refill(rnd):
    for x in range(n):
        temp = []
        for y in range(len(garage[rnd+1][x])):
            value = garage[rnd+1][x][y]
            if value != 0:
                temp.append(value)
            
    garage[rnd+1][x] = temp

 

이제 dfs함수를 보자.

현재 칸과 인접한 칸을 찾으면서 각종 값을 업데이트한다.

해당 칸의 상하좌우 칸에 대해 자신과 색이 같고 아직 방문된 적 없는 칸이라면 dfs를 부른다.

dx = [0,1,0,-1]
dy = [1,0,-1,0]
def dfs(rnd, count, x, y, visit, left, right, bottom, top, neighbor):
    count += 1
    color = garage[rnd][x][y]
    neighbor.append([x,y]) #나중에 지워야 할 칸
    visit[x][y] = True
    left,right = min(left, x), max(right, x)
    bottom,top = min(bottom, y), max(top, y)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx <=n-1 and 0 <= ny <= n-1 and garage[nx][ny] == color and visit[nx][ny] == False:
            count, left, right, bottom, top, neighbor = dfs(rnd, count, nx, ny, visit, left, right, bottom, top, neighbor)
    
    return count, left, right, bottom, top, neighbor

 

이 함수는 차고 범위 안에서 인접한 차와 같은 색의 차가 있는지 확인하는 함수이다.

def calculateNeighbor(rnd):
    hasNeighbor = [[0 for _ in range(n)] for _ in range(n)]
    for x in range(n):
        for y in range(n):
            if x<n-1 and garage[rnd][x][y] == garage[rnd][x+1][y]:
                hasNeighbor[x][y] = hasNeighbor[x+1][y] = 1
            if y<n-1 and garage[rnd][x][y] == garage[rnd][x][y+1]:
                hasNeighbor[x][y] = hasNeighbor[x][y+1] = 1