[백준/삼성SW역량테스트] 21609 상어 중학교 (Python)

✏️ 문제

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

✏️ 풀이

1번 ~ 5번 과정을 블록그룹이 없을 때까지 수행한다.

은근히 자잘한 조건이 많기 때문에 1번~5번 구현하면서 코드 길어지기 전에 중간중간 정확하게 구현했는지 테스트해야 풀기가 편할 것 같다.

 

<1번>

각 좌표에 대해서 BFS 돌면서 최대 크기의 블록그룹을 구한다.

이 때 블록그룹에 일반 블록이 무조건포함되어야 하므로 일반 블록일때만 해당 동작을 수행한다.

 

격좌를 BFS로 돌면서 해당 블록그룹의 개수를 구한다.

1) 블록그룹의 개수가 최대이고, 같은 경우 2) 무지개 블록 개수가 최대인 좌표를 찾는다.

3) 무지개 블록 수까지 같은 경우 행, 열이 가장 큰 블록그룹을 선택한다.

이 때 주의해야 할 점은 BFS 시작 좌표끼리 비교하는 것이 아니라, "블록그룹의 기준좌표"를 비교하는 것이다.

 

즉, BFS를 돌면서 해당 블록그룹에서 가장 행, 열이 작은 기준 좌표를 구해서 이 기준 좌표도 같이 저장해서 비교해줘야 한다.

( 문제 풀면서 이 부분이 가장 헷갈렸다. 이 부분 구현 안하면 예시 테케에서는 안 걸리는 데 채점하면 틀렸다고 나온다 )

 

BFS를 다 돌고나서 만약 최대 그룹의 크기가 1이면, 블록그룹이 없다는 뜻이므로 (문제에서 정의한 블록그룹의 크기는 최소2)

게임을 종료한다.

 

<2번>

찾은 블록그룹의 모든 블록을 BFS로 제거한다. (-2로 표시 )

해당 블록그룹의 크기의 제곱만큼 점수에 더한다.

 

<3번>

맨 밑줄의 윗줄부터, 위로 올라가면서 아래 동작을 수행한다.

 

현재 줄의 밑 줄부터 마지막 줄까지 세로로 탐색하면서, 비어있는 곳이 있는 지 찾는다. 

이 때 중간에 다른 블록이 있다면 더 이상 내려가지 않는다.

비어있는 곳 중 가장 아래 쪽의 좌표로 블록을 옮긴다.

 

<4번>

반시계 방향으로 90도 돌리는 작업을 수행한다.

이 부분은 직접 그려보면 쉽게 규칙을 파악할 수 있다.

X' = N  - 1 - Y, 'Y = X 가 된다. 

새로운 배열을 생성해서 90도 돌아간 격좌를 대입하고, 다시 원래 배열에 복사해주었다.

 

<5번>

3번을 한번 더 수행한다. 똑같은 작업이라 함수로 빼주었다.

✏️ 코드

from collections import deque

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

N, M = map(int, input().split())
arr = [] # N * N 격자
for _ in range(N):
    arr.append(list(map(int, input().split())))

def bfs(i, j):
    checked = [[False]*N for _ in range(N)]
    dq = deque()
    dq.append((i, j)) # 좌표, 블록 크기, 무지개 블록 수
    checked[i][j] = True
    cnt, rainbow_cnt = 1, 0

    min_x, min_y = i, j

    while dq:
        x, y = dq.popleft()

        # 블록그룹의 기준 좌표 구하기 (무지개 블럭은 제외)
        if arr[x][y] != 0:
          min_x, min_y = min((min_x, min_y), (x, y))

        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]

            if 0<=nx<N and 0<=ny<N and not checked[nx][ny]: # 검정블록, 빈 블록은 범위에 포함안됨 # 색깔 같아야함
                checked[nx][ny] = True
                if arr[nx][ny] == 0: # 무지개 블록
                    cnt += 1
                    rainbow_cnt += 1
                    dq.append((nx, ny))
                elif arr[nx][ny] == arr[i][j]: # 같은 색깔 일반 블록
                    cnt += 1
                    dq.append((nx, ny))

    return cnt, rainbow_cnt, min_x, min_y

def gravity():
    for i in range(N-2, -1, -1): # 맨 밑 윗줄 부터 거꾸로 ( 맨 밑줄은 할 필요 X )
        for j in range(N):
            if arr[i][j] >= 0:
                nx = i
                for k in range(i+1, N):
                    if arr[k][j] != -2: # 막힘
                        break
                    else:
                        nx = k
                if nx != i:
                    arr[nx][j] = arr[i][j]
                    arr[i][j] = -2
total_score = 0

while True:
    # 1번
    max_cnt, max_rainbow_cnt, max_x, max_y = 1, 0, -1, -1
    for i in range(N):
        for j in range(N):
            if arr[i][j] > 0: # BFS를 일반 블록에서만 시작 (꼭 하나 이상 포홤해야 하므로)

                # i, j에서 만들어진 블록의 기준 좌표를 비교해야 하는 것
                cnt, rainbow_cnt, std_x, std_y = bfs(i, j)

                if cnt > max_cnt:
                    max_x, max_y = std_x, std_y
                    max_cnt = cnt
                    max_rainbow_cnt = rainbow_cnt
                elif cnt == max_cnt:
                    if rainbow_cnt > max_rainbow_cnt:
                        max_x, max_y = std_x, std_y
                        max_rainbow_cnt = rainbow_cnt
                    elif rainbow_cnt == max_rainbow_cnt:
                        if std_x > max_x:
                            max_x, max_y = std_x, std_y
                        elif std_x == max_x:
                            if std_y > max_y:
                                max_x, max_y = std_x, std_y

    if max_cnt==1: # 블록 그룹 없음 - 게임 종료
        break

    # 2번 ( 모든 블록 제거 )
    # 찾은 max_x, max_y 에서 시작해서 BFS로 다 -2로 변경
    dq = deque()
    dq.append((max_x, max_y))
    color = arr[max_x][max_y]
    arr[max_x][max_y] = -2
    while dq:
        x, y = dq.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < N and 0 <= ny < N and (arr[nx][ny] == 0 or arr[nx][ny] == color):
                arr[nx][ny] = -2
                dq.append((nx, ny))

    total_score += max_cnt ** 2

    # 3번 ( 중력 작용 )
    gravity()

    # 4번 ( 90도 반시계 회전 )
    new_arr = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_arr[N-1-j][i] = arr[i][j]

    for i in range(N):
        for j in range(N):
            arr[i][j] = new_arr[i][j] # 복사

    # 5번 ( 중력 작용 )
    gravity()

print(total_score)

✏️ 다른 사람 풀이 

1 ~ M 번 색깔 별로 BFS 돌면서 가장 큰 블록그룹을 찾는다.

 

위 풀이에서 M을 안쓴게 찝찝했는데 M 굳이 준 이유가 이렇게 풀으라고 준 것 같다...

같은 그룹을 여러번 탐색할 일이 없어지니까 훨씬 나은 풀이인 것 같다.

✏️ 생각

테케는 다 돌아가는데 채점 실패했을 때 빠트린 조건 없는지 다시 한번 꼼꼼히 보자

은근히 중력 작용, 반시계/시계 방향 배열 회전시키는 부분은 삼성 기출에서 자주 봐서 흐름을 외워두는 게 좋을 것 같다.

코드가 뭔가 지저분하고 길다.. 위에 방법으로 다시 풀어봐야겠다.