[BOJ] 21609번 상어 중학교 (Python) [삼성 SW 역량 테스트 기출 문제] - 중요

문제

https://www.acmicpc.net/problem/21609
2021 상반기 삼성 SW역량테스트 기출문제이다.

풀이

AC까지 시간이 굉장히 오래걸렸다. 총 1시간 40분이 걸려서 다시 풀 때 시간단축을 중점에 둬야 할 것 같다.

N<=20, M<=5를 보고 극악의 시간복잡도를 확신했고, 노트에 손으로 전체적인 플로우를 어떻게 가져갈지 적고 들어갔다. 이건 조금 복잡한 시뮬레이션이면 꼭 필요한 단계인 것 같다.

2차원 배열 시계회전, 반시계회전은 zip을 통해 간단하게 구현 가능하다
이때, 다음부터는 함수로 빼는게 코드 가독성 측면에서 좋을 것 같다.

def rotate(graph): # 시계회전
    return list(map(list,zip(*graph[::-1])))

def rotate_reverse(graph): # 반시계회전
    return list(map(list,zip(*graph)))[::-1]

중력으로 당기는 것도 이전 기출인 2048(Easy)에서 봤던 방법이다. 이때 나는 1차원에서 중력 방향으로 땅기는 걸 먼저 생각하고 이를 2차원에 적용했는데, 차이점은 이번 문제의 경우 중간에 땡겨지면 안되는 제약조건이 섞여있다.

이때, 당기는걸 할때, 옮길 곳을 찾고 한번에 당기는게 아니라 한칸한칸 SWAP해가면서 구현하도록 할 수 있다. + 2차원에서 당기는 것도 2중 for문으로 한번에 가능(참고풀이)

# 1차원 배열에서 왼쪽으로 빈곳 통과해서 당기기
def move(one_list):
    for from_idx in range(1,N):
        check_idx = from_idx -1
        while check_idx >= 0 and one_list[check_idx] == EMPTY:
            # SWAP
            one_list[check_idx],one_list[check_idx+1] = one_list[check_idx+1],one_list[check_idx]
            check_idx -= 1

# 2차원 배열에서 아래로 빈곳 통과해서 당기기
def move(graph):
    for y in range(N): # y좌표: 0~N-1
        for from_idx in reversed(range(N-1)): # 당길 x좌표: N-2,N-1,...0
            check_idx = from_idx + 1
            while check_idx <= N-1 and graph[check_idx][y] == EMPTY:
                # SWAP
                graph[check_idx][y],graph[check_idx-1][y] = graph[check_idx-1][y], graph[check_idx][y]
                check_idx += 1

삼성에서 배열 돌리기, 중력 작용은 확실히 자주 나오므로 익숙해지자.

추가로 수정할 부분이 생겨서 수정을 했는데, 형태만 비슷한 완전 엉뚱한 곳을 수정하는 실수가 있었다. 에러가 안났으면 그냥 넘어갈 뻔해서 수정할 때 내가 수정하는 곳이 정확히 맞는지 확인하고 수정해야겠다.

중간에 문제를 잠깐 끊어서 그런 것도 있지만, 문제를 확실히 짚지 않고 대충 코드를 작성한 부분이 있었다. 문제를 꾹꾹 눌러 확실하게 머리에 넣은 뒤에 코드 타이핑을 하자. 조금이라도 애매한 부분이 있으면 코드로 넘어가지 말고 문제 이해에 시간을 더 써야 한다.

from collections import deque

EMPTY, BLACK, RAINBOW = -float('inf'), -1, 0 # 1이상은 일반블록
DX_DY = [(0,1),(1,0),(0,-1),(-1,0)]

def print_graph(graph):
    """디버깅용"""
    for g in graph:
        print(g)

def is_valid(i,j):
    """범위에 있는지만 체크"""
    if 0<=i<N and 0<=j<N:
        return True
    return False

def two_d_move(graph):
    # 시계 회전
    graph = list(map(list,zip(*graph[::-1])))

    # 각 row별 1차원 중력 적용
    for g in graph:
        one_d_move(g)

    # 반시계 회전
    graph = list(map(list,zip(*graph)))[::-1]

    return graph

def one_d_move(one_list):
    """1차원 리스트에서 왼쪽으로 중력 작용"""
    for from_idx in range(1,N): # 1~N-1
        if one_list[from_idx] >= 0: # 일반&무지개 블록
            change_idx = 0
            for j in reversed(range(from_idx)): # 0~i-1
                if one_list[j] >= -1: # 다른블록 만나면
                    change_idx = j+1
                    break
            
            if change_idx != from_idx:
                one_list[change_idx] = one_list[from_idx]
                one_list[from_idx] = EMPTY

def bfs(i,j):
    """(i,j) 일반블록에서 만들 수 있는 최대 블록 그룹 구해서 정보 반환"""
    # !EMPTY도 고려해야됨
    visited = [[False]*N for _ in range(N)]
    visited[i][j] = True
    block_group_ij_list = [(i,j)]
    queue = deque([(i,j)])
    same_color = graph[i][j]

    while queue:
        x,y = queue.pop()
        for dx, dy in DX_DY:
            check_x = x+dx
            check_y = y+dy
            if is_valid(check_x,check_y) and not visited[check_x][check_y]\
            and graph[check_x][check_y] in [RAINBOW, same_color]:
                visited[check_x][check_y] = True
                queue.appendleft((check_x,check_y))
                block_group_ij_list.append((check_x,check_y))

    # rainbow_cnt 구하기
    rainbow_cnt = sum(1 for i,j in block_group_ij_list if graph[i][j] == RAINBOW)

    # main_block_ij 구하기
    for i,j in sorted(block_group_ij_list): # (i,j) 오름차순
        if graph[i][j] > 0: # 일반 블록
            main_block_ij = (i,j)
            break
    
    return block_group_ij_list,rainbow_cnt, main_block_ij
    

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

score = 0

while True:
    block_cand = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] > 0: # 일반&무지개블록
                ij_list, rainbow_cnt, main_blocK_ij = bfs(i,j)
                if len(ij_list) >= 2: # 블록 2개 이상이어야 블록그룹
                    block_cand.append((ij_list, rainbow_cnt, main_blocK_ij))
    
    if not block_cand: # 블록그룹 없으면 종료
        break

    block_cand.sort(key = lambda x: (-len(x[0]),-x[1],-x[2][0],-x[2][1]))

    delete_ij_list = block_cand[0][0] # 제거할 좌표들
    score += (len(delete_ij_list)**2) # 점수 획득

    # 제거하기
    for i, j in delete_ij_list:
        graph[i][j] = EMPTY

    # 중력 작용
    graph = two_d_move(graph)

    # !반시계 회전
    graph = list(map(list, zip(*graph)))[::-1]

    # 중력 작용
    graph = two_d_move(graph)

print(score)