[CodeTree] 색깔 폭탄 - 삼성 SW 역량테스트 2021 상반기 오전 2번 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 분석

• -1, 0, 1이상의 숫자로 이루어진 N*N 격자가 주어지며, -1은 벽, 0은 빨간색 폭탄, 1이상의 수는 서로 다른 색상의 폭탄이 들어있음을 의미.
• 폭탄 묶음이란, 두 개 이상의 폭탄으로 이루어진 폭탄 그룹을 의미하며, 모두 동일한 색상의 폭탄으로 이뤄져 있어야 함. 
• 빨간색 폭탄으로만 이루어졌거나, 빨간색을 제외하고 다른 두 색상이 함께 묶인 그룹은 정상적인 묶음이 아님.
• 각 Turn마다 우선순위에 따라 폭탄 그룹을 삭제하는 작업을 수행함. 우선순위는 아래와 같음.
  • 크기가 가장 큰 묶음.
  • 빨간 색 폭탄의 수가 가장 적은 묶음.
  • 묶음 내 폭탄의 row가 큰 순서대로, 묶음 내 폭탄의 col이 작은 순서대로.
• 폭탄 그룹 제거 과정이 종료되면, 중력 -> 반시계 방향 90도 회전 -> 중력이 순서대로 수행됨.
• 중력이란 가능한 원소들을 아래로 이동시키는 작업을 의미하며, 벽 아래로는 이동할 수 없음.
• 더 이상 폭탄 묶음이 존재하지 않을 때까지 반복하여 수행.
• 없어진 폭탄의 **2만큼 score를 획득하며, total score를 return하는 문제.

 

문제 접근

• 폭탄의 그룹을 구할 때, BFS 알고리즘 활용
  • 빨간 폭탄의 경우 방문 처리를 해버리면 다른 인접한 블록이 해당 폭탄에 접근이 가능함에도 불구하고, 접근하지 못하는 case가 발생하기에, set() 자료구조를 활용하여 따로 방문 처리 수행.
  • 탐색하지 않아도 되는 값 (-1: 벽, -2: 비어있는 칸, 0: 빨간 블록)은 pass하도록 작성.
  • (그룹의 크기, 빨간 블록 수, 최대 row 값, 최소 col값)을 candits에 저장하여 관리. 
  • candits (제거 가능한 블록 그룹 후보)의 크기가 0일 때 종료, 그렇지 않을 경우 위 과정을 반복적으로 수행.
• 반시계 방향으로 회전시키는 rotate_left 함수 선언
  • 좌표계를 활용하여 값을 변경할 수 있지만, list comprehension을 활용하여 간단 명료하게 구현.
• 중력 작용 구현을 위한 gravity 함수 선언
  • row를 탐색하는 i, 맨 아래부터 순차적으로 빈 칸을 찾는 j, j와 교체 가능한 값을 탐색하는 k 총 3개의 변수를 활용하여 이동 가능한 블록들을 아래부터 차례대로 채워나가는 로직 구현

소스 코드

# define lib
from collections import deque

# set value from input
n, m = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
score = 0

# define func
def rotate_left(arr):
    return [list(matrix) for matrix in list(zip(*arr))[::-1]]

def gravity(arr):
    for i in range(n):
        j = n-1
        while j > 0: 
            if arr[j][i] != -2:
                j -= 1
                continue
            for k in range(j-1, -1, -1):
                if arr[k][i] == -1:
                    j = k
                    break

                if arr[k][i] >= 0:
                    arr[k][i], arr[j][i] = arr[j][i], arr[k][i]
                    break
            j -= 1
    return arr

# run loop
while True:
    candits = [] # size, len_red_pts, max_c, min_r

    # brute force
    visit = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visit[i][j] or field[i][j] <= 0:
                continue
            
            visit[i][j] = True
            group, red_pts, queue = [(i, j)], set(), deque([(i, j)])
            while queue:
                cx, cy = queue.popleft()
                for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                    nx, ny = cx+dx, cy+dy
                    if nx < 0 or nx >= n or ny < 0 or ny >= n or visit[nx][ny]:
                        continue
                        
                    if field[nx][ny] == 0 and (nx, ny) not in red_pts:
                        red_pts.add((nx, ny))
                        queue.append((nx, ny))

                    elif field[nx][ny] == field[i][j]:
                        group.append((nx, ny))
                        visit[nx][ny] = True
                        queue.append((nx, ny))
            
            if len(group) + len(red_pts) == 1:
                continue
            max_r, min_c = max([k[0] for k in group]), min([k[1] for k in group])
            candits.append((len(group)+len(red_pts), len(red_pts), max_r, min_c, group + list(red_pts)))
    
    # exit flag
    if not candits:
        break

    # remove 
    candits.sort(key=lambda x: (-x[0], x[1], -x[2], x[3]))
    for gx, gy in candits[0][-1]:
        field[gx][gy] = -2
    score += int(len(candits[0][-1])**2)

    field = gravity(field)
    field = rotate_left(field)
    field = gravity(field)

print(score)

 

- 제출 횟수: 1회

- 풀이 시간: 40분