[백준, 삼성 기출] 21609_상어 중학교 (Python) - 다시 풀기

21609_상어 중학교 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 2)
• 링크 : 21609번: 상어 중학교

1. 기록

• 22/04/21 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 가장 큰 블록 그룹을 만들기 위해 dfs를 돌린다.

>> 그러한 블록 그룹이 여러개라면
>> 1. 무지개 블록의 수가 가장 많은 블록 그룹

>> 그러한 블록 그룹이 여러개라면
>> 2. 기준 블록의 행이 가장 큰 것을,

>> 그러한 블록 그룹이 여러개라면
>> 3. 열이 가장 큰 것을 찾는다.

>> BFS를 돌렸을 때 해당 색깔블록이 뭐지 카운트해준다.(color)
>> 무지개 블록의 갯수도 카운트해준다. (rainbow)
>> 검정 블록은 카운트해주지 않는다. (black)
>> 최대의 색깔블록 + 무지개블록 칸을 없애주고 점수를 매겨준다. (total_block)
>> 최대의 total_block 을 계속 생신해주면서 최댓값을 찾는다.

>> 중력 작용 (칸을 벗어나기 직전까지 또는 이동하려는 칸에 다른 블록이 있을때 까지)
>> 검은색 블록 -1 은 움직이지 않는다.
>> dx = [1]
>> dy = [0]

>> 반시계방향으로 회전
>> 행이 열로 바뀜
>> 열이 일정하면서 최대인경우 최소 행으로 바뀜
>> 열이 일정하면서 최소인경우 최대 행으로 바뀜


2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5 3
2 2 -1 3 1
3 3 2 0 -1
0 0 0 1 2
-1 3 1 3 2
0 3 2 2 1

- 예제 출력 1 -
77

- 예제 입력 2 -
6 4
2 3 1 0 -1 2
2 -1 4 1 3 3
3 0 4 2 2 1
-1 4 -1 2 3 4
3 -1 4 2 0 3
1 2 2 2 2 1

- 예제 출력 2 -
125

- 예제 입력 3 -
4 3
1 1 1 3
3 2 3 3
1 2 -1 3
-1 -1 1 1

- 예제 출력 3 -
33

(3) 코드

from collections import deque
from pprint import pprint

# 인접 블록 찾기 -> 블록 크기, 무지개크기, 블록좌표 리턴
def bfs(x, y, color):
    q = deque()
    q.append([x, y])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    block_cnt, rainbow_cnt = 1, 0  # 블록개수, 무지개블록 개수
    blocks, rainbows = [[x, y]], []  # 블록좌표 넣을 리스트, 무지개좌표 넣을 리스트

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

            # 범위 안이면서 방문 안한 일반 블록인 경우
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and a[nx][ny] == color:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                blocks.append([nx, ny])

            # 범위 안이면서 방문 안한 무지개 블록인 경우
            elif 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and a[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                rainbow_cnt += 1
                rainbows.append([nx, ny])

    # 무지개블록은 방문 다시 해제
    for x, y in rainbows:
        visited[x][y] = 0

    return [block_cnt, rainbow_cnt, blocks + rainbows]


# 블록 제거 함수
def remove(block):
    for x, y in block:
        a[x][y] = -2


# 중력 함수
def gravity(a):
    for i in range(N - 2, -1, -1):  # 밑에서 부터 체크
        for j in range(N):
            if a[i][j] > -1:  # -1이 아니면 아래로 다운
                r = i
                while True:
                    if 0 <= r + 1 < N and a[r + 1][j] == -2:  # 다음행이 인덱스 범위 안이면서 -2이면 아래로 다운
                        a[r + 1][j] = a[r][j]
                        a[r][j] = -2
                        r += 1
                    else:
                        break


# 반시계 회전 함수
def rot90(a):
    new_a = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_a[N - 1 - j][i] = a[i][j]
    return new_a


# 0. 메인코드
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]

# N = int(5)
# M = int(3)
# a = [[2, 2, -1, 3, 1],
#  [3, 3, 2, 0, -1],
#  [0, 0, 0, 1, 2],
#  [-1, 3, 1, 3, 2],
#  [0, 3, 2, 2, 1]]

score = 0  # 점수

# 1. 오토플레이-> while {2. 크기 가장 큰 블록 찾기 3. 블록제거+점수더하기 4. 중력 5. 90회전 6. 중력}
while True:
    # 2. 크기 가장 큰 블록 찾기
    visited = [[0] * N for _ in range(N)]  # 방문체크
    blocks = []  # 가능한 블록 그룹들 넣을 리스트
    for i in range(N):
        for j in range(N):
            if a[i][j] > 0 and not visited[i][j]:  # 일반블록이면서 방문 안했으면
                visited[i][j] = 1  # 방문
                block_info = bfs(i, j, a[i][j])  # 인접한 블록 찾기
                pprint(block_info)
                # block_info = [블록크기, 무지개블록 개수, 블록좌표]
                if block_info[0] >= 2:
                    blocks.append(block_info)
    blocks.sort(reverse=True)

    # 3. 블록제거+점수더하기
    if not blocks:
        break
    remove(blocks[0][2])
    score += blocks[0][0] ** 2

    # 4. 중력
    gravity(a)

    # 5. 90회전
    a = rot90(a)

    # 6. 중력
    gravity(a)

print(score)

(4) 정리

시험에서 이렇게 코드 짤 수 있을지 의문이다.

내가 생각하는 포인트

1. 이미 visited된 곳은 블록 카운트 시도하지 않는 것
2. rainbow 블록은 visited 초기화
3. 블록 좌표들을 하나하나 다 append 해서 점수를 매길때 해당 좌표 블록은 삭제하는 것 (코드에서는 -2라는 값을 할당함)
4. 중력함수 짜는 것 -> 이동하려는 칸이 비어있으면 계속 내려오게끔 코드가 짜여져 있음
5. 90도 반시계방향 회전하는 코드 어떻게 바로 생각해 내는지

(5) 참고

참고 풀이