[Samsung] 2021-2 오전 2번 색깔 폭탄

April 6, 2023

[Samsung] 2021-2 오전 2번 색깔 폭탄

Question

Language: Python

Difficulty: Gold 2

해당 문제에서 구현해야될 부분은 크게 4가지이다.

가장 큰 폭탄 묶음 찾기
폭탄 제거
중력 작용
반시계 회전

각 세부 과정은 아래와 같다

가장 큰 폭탄 묶음 찾기 각 좌표에 대해 인접한 좌표의 색깔을 비교해서 같은 색이거나 빨간색 인경우 폭탄 묶음에 포함시킨다. 각각의 폭탄 묶음을 처리할 때 기준점이 되는 좌표 또한 갱신한다. 추가적으로 빨간색 폭탄의 경우 따로 배열에 저장하여 나중에 활용할 수 있도록 한다.

같은 색깔, 혹은 빨간색 폭탄에 대한 폭탄 묶음을 구하고 난 이후, 폭탄 묶음이 유효한지 여부를 판단해야한다. 폭탄 묶음 내 폭탄의 갯수가 2개 이상이어야 하며 빨간색으로만 이루어지지 않았는지 판단한다. 빨간색 폭탄의 경우 모든 색깔의 폭탄에 대해서 공유가 가능하기 때문에 하나의 폭탄에 대한 폭탄 묶음을 처리하고 난 이후에는 방문해제 처리를 해줘야 다른 폭탄도 처리가 가능하다.

이후, 폭탄 묶음에 대한 배열에 대해 정렬을 수행한다. 폭탄의 묶음 내 폭탄의 갯수가 가장 많은순, 빨간색 폭탄의 갯수가 가장 적은 순, 기준점의 행이 큰 순, 열이 작은순으로 정렬을 수행해서 가장 우선순위가 높은 폭탄 묶음을 찾아낸다.

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

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

    components=[]

    for start_row in range(n):
        for start_col in range(n):
            color=board[start_row][start_col]
            #이전에 방문하였거나 빨간색인 경우 처리하지 않는다.
            if visited[start_row][start_col] or color <=0 :
                continue
            
            queue=deque([(start_row,start_col)])

            #기준점
            base_row,base_col=start_row,start_col

            #빨간점들의 좌표
            red_coordinates=[]
            red_count=0

            component=[]
            component_count=0

            while queue:
                row,col=queue.popleft()
                #이전에 방문했는지 검사
                if visited[row][col]:
                    continue
                visited[row][col]=True

                component.append((row,col))
                component_count+=1
                #빨간색인 경우 따로 배열에 추가로 관리한다.
                if board[row][col]==0:
                    red_coordinates.append((row,col))
                    red_count+=1
                
                #빨간색이 아닌 점의 경우기준점 갱신
                elif row > base_row or (row == base_row and col < base_col):
                    base_row,base_col=row,col

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

                    #좌표의 범위 검증, 빈칸 검증, 색깔 검증
                    if not check_range(next_row,next_col) or board[next_row][next_col] == -2 or (board[next_row][next_col] != color and board[next_row][next_col] != 0):
                        continue
                    
                    queue.append((next_row,next_col))
    
            #폭탄 묶음의 크기는 무조건 2이상이어야 하며, 빨간색으로만 이루어져서는 안된다.    
            if component_count >=2 and component_count != red_count:
                components.append((component_count,red_count,base_row,base_col,component))

            #빨간색 폭탄의 경우 공용으로 사용되기 때문에 방문 해제 처리를 해야한다.
            for row,col in red_coordinates:
                visited[row][col]=False
    
    components.sort(key=lambda x: (-x[0],x[1],-x[2],x[3]))
    return components

폭탄 제거

폭탄 묶음 내에 폭탄을 제거하고 해당 자리는 -2를 삽입해서 빈칸임을 표시한다. 폭탄을 제거한 갯수의 제곱 만큼을 점수로 반환한다.

#폭탄 묶음 제거
def explosion(board,component):
    count=0
    for row, col in component:
        board[row][col]=-2
        count+=1
    
    return count**2

중력 작용

검은색 돌이 아닌 폭탄에 대해 아래에 빈칸이 있는 경우 내릴 수 있을 만큼 계속 내린다.

#중력의 작용
def gravity(board):
    
    for col in range(n):
        for row in range(n-1,-1,-1):

            #검은색 돌이거나, 빈칸 인경우 중력이 작용하지 않는다.
            if board[row][col]==-1 or board[row][col] == -2:
                continue
            
            #아래의 행이 빈칸 인 경우에만 이동하도록 한다.
            target_row=row
            while target_row < n-1 and board[target_row+1][col] ==-2:
                target_row+=1
            
            #이동한 경우에만 이동을 반영한다.
            if target_row != row:
                board[target_row][col]=board[row][col]
                board[row][col]=-2

반시계 회전

반시계 회전의 경우 좌표의 평행이동을 고려하여 새로운 배열을 반환하는 작업을 진행한다.

#반시계 방향 회전
def rotate_counter_clockwise(board):
    new_board=[[-2] * n for _ in range(n)]
    
    for row in range(n):
        for col in range(n):
            new_board[n-col-1][row]=board[row][col]

    for row in range(n):
        for col in range(n):
            board[row][col]=new_board[row][col]

Solution

from collections import deque

#폭탄 묶음을 찾는 함수
def find_components():
    visited=[[False] * n for _ in range(n)]

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

    components=[]

    for start_row in range(n):
        for start_col in range(n):
            color=board[start_row][start_col]
            #이전에 방문하였거나 빨간색인 경우 처리하지 않는다.
            if visited[start_row][start_col] or color <=0 :
                continue
            
            queue=deque([(start_row,start_col)])

            #기준점
            base_row,base_col=start_row,start_col

            #빨간점들의 좌표
            red_coordinates=[]
            red_count=0

            component=[]
            component_count=0

            while queue:
                row,col=queue.popleft()
                #이전에 방문했는지 검사
                if visited[row][col]:
                    continue
                visited[row][col]=True

                component.append((row,col))
                component_count+=1
                #빨간색인 경우 따로 배열에 추가로 관리한다.
                if board[row][col]==0:
                    red_coordinates.append((row,col))
                    red_count+=1
                
                #빨간색이 아닌 점의 경우기준점 갱신
                elif row > base_row or (row == base_row and col < base_col):
                    base_row,base_col=row,col

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

                    #좌표의 범위 검증, 빈칸 검증, 색깔 검증
                    if not check_range(next_row,next_col) or board[next_row][next_col] == -2 or (board[next_row][next_col] != color and board[next_row][next_col] != 0):
                        continue
                    
                    queue.append((next_row,next_col))
    
            #폭탄 묶음의 크기는 무조건 2이상이어야 하며, 빨간색으로만 이루어져서는 안된다.    
            if component_count >=2 and component_count != red_count:
                components.append((component_count,red_count,base_row,base_col,component))

            #빨간색 폭탄의 경우 공용으로 사용되기 때문에 방문 해제 처리를 해야한다.
            for row,col in red_coordinates:
                visited[row][col]=False
    
    components.sort(key=lambda x: (-x[0],x[1],-x[2],x[3]))
    return components

#폭탄 묶음 제거
def explosion(board,component):
    count=0
    for row, col in component:
        board[row][col]=-2
        count+=1
    
    return count**2

#중력의 작용
def gravity(board):
    
    for col in range(n):
        for row in range(n-1,-1,-1):

            #검은색 돌이거나, 빈칸 인경우 중력이 작용하지 않는다.
            if board[row][col]==-1 or board[row][col] == -2:
                continue
            
            #아래의 행이 빈칸 인 경우에만 이동하도록 한다.
            target_row=row
            while target_row < n-1 and board[target_row+1][col] ==-2:
                target_row+=1
            
            #이동한 경우에만 이동을 반영한다.
            if target_row != row:
                board[target_row][col]=board[row][col]
                board[row][col]=-2

 
#반시계 방향 회전
def rotate_counter_clockwise(board):
    new_board=[[-2] * n for _ in range(n)]
    
    for row in range(n):
        for col in range(n):
            new_board[n-col-1][row]=board[row][col]

    for row in range(n):
        for col in range(n):
            board[row][col]=new_board[row][col]

#좌표의 범위 검증
def check_range(row,col):
    if row < 0 or row>=n or col < 0 or col>=n:
        return False
    return True

def solution():
    total_score=0
    
    while True:
        components=find_components()
        #더 이상 폭탄 묶음이 없는 경우에는 종료
        if len(components)==0:
            break
        
        #가장 우선순위가 큰 폭탄 묶음 제거
        score=explosion(board,components[0][4])
        total_score+=score
        
        #중력 작용
        gravity(board)
        
        #반시계 방향 회전
        rotate_counter_clockwise(board)

        #중력 작용
        gravity(board)
 
    print(total_score)

if __name__ =="__main__":
    n,m=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(n)]

    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2021-2 오전 2번 색깔 폭탄

[Samsung] 2021-2 오전 2번 색깔 폭탄

Question

Language: Python

Difficulty: Gold 2

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기