[백준] 21609. 상어 중학교 (파이썬)

문제

상어 중학교

오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

 

시간 제한 1초 (추가 시간 없음)

메모리 제한 1024MB

 

• 오토 플레이란? 상어 중학교 코딩 동아리에서 만든 게임이다.
• 공간의 크기 N x N
• 블록의 종류 : 검은색(-1), 무지개색(0), 일반 블록(M가지 색상, 1~M 사이 자연수로 표현)
• 인접한 칸 : 상하좌우로 접해 있는 경우를 지칭
• 블록 그룹이란?
  • 연결된 블록의 집합
  • 일반 블록을 적어도 하나 이상 포함
  • 일반 블록의 색은 모두 같아야 함
  • 검은색 블록은 포함시키지 말 것
  • 블록의 수는 2개 이상
  • 모두 인접해 있어야 함

• 게임의 오토 플레이 기능
  1.  블록 그룹들 중, 크기 > 무지개 블록의 수 > 기준 블록의 행 > 기존 블록의 열 기준으로 큰 값을 지닌 블록 그룹을 선택.
  2.  1에서 찾은 블록 그룹의 모든 블록 제거. 블록 그룹에 포함된 블록의 수를 B라고 할때, B^2점을 획득한다.
  3.  격자에 중력이 작용한다.
  4.  격자가 90도 반시계 방향으로 회전한다.
  5.  다시 격자에 중력이 작용한다.
• 격자에 중력이 작용하면, 검은색 블록을 제외한 모든 블록의 행의 번호가 큰 칸으로 (down) 이동한다.
• 이동 시, 다른 블록이나 격자의 경계를 만나면 멈춘다.

---

풀이

상어 중학교 문제는 구현량이 많고, 요약해도 다소 복잡하므로 차근차근 잘 따라오세요!!

 

핵심 알고리즘

1.  크기가 가장 큰 블록 그룹을 찾는다. -> find_block()

• 블록 그룹에는 적어도 하나의 일반 블록이 포함되어야 함 -> 격자(block)을 완전 탐색
• 완전 탐색 중에 일반 블록을 발견 시, 인접한 블록을 탐색하며 블록 그룹을 찾는다. -> BFS
• 정렬 기준에 맞게 가장 큰 블록 그룹 선택

2.  모든 블록 제거 -> remove_block()
3.  격자에 중력 작용 -> gravity()

4.  격자가 90도 반시계 방향으로 회전 -> rotate_block()

5.  다시 격자에 중력 작용 -> gravity()

6.  1~5의 과정 반복

 

옵션 1.  블록 그룹이 더 이상 존재하지 않으면 획득한 점수 출력  -> 종료 조건

 

이 문제에서의 핵심 구현 포인트를 살펴보자.

1. 크기가 가장 큰 블록 그룹 찾기 

# 1. 크기가 가장 큰 블록을 찾는다. BFS
def find_block(i, j, block_num):

	q = deque()
	q.append((i, j))

	normals = [[i, j]] # 일반 블록 위치 저장
	rainbows = [] # 무지개 블록 위치 저장

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

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

			if 0<=nx<n and 0<=ny<n:
				#무지개 블록을 만난 경우 : rainbows에 추가
				if block[nx][ny] == 0 and not visited[nx][ny]:
					q.append((nx, ny))
					rainbows.append([nx, ny])
					visited[nx][ny] = 1
				
                		#일반 블록을 만난 경우 : normals에 추가
				elif block[nx][ny] == block_num and not visited[nx][ny]:
					q.append((nx, ny))
					normals.append([nx, ny])
					visited[nx][ny] = 1
	
	for x, y in rainbows: # **무지개 블록들은 visited = False 처리
		visited[x][y] = 0

	# 정렬 기준에 맞게 return : <블록 수, 무지개 블록 수, 그룹 내 불록들 위치 정보(행, 열)> 
	return [len(normals + rainbows), len(rainbows), normals + rainbows]


while True:
	visited = [[0] * n for _ in range(n)] # 방문 여부 표시
	groups = [] # 블록 그룹 저장

	for i in range(n):
		for j in range(n):
			if block[i][j] >= 1 and not visited[i][j]: # 아직 방문하지 않은 일반 블록을 찾으면
				visited[i][j] = 1 # 방문 표시
				group = find_block(i, j, block[i][j]) # BFS를 통해 블록 그룹 찾기

				if group[0] >= 2: # 길이가 2 이상이면 groups에 추가
					groups.append(group)
	
	groups.sort(reverse = True) # 가장 큰 블록 그룹을 찾기 위해 정렬

이 문제의 가장 핵심인 크기가 가장 큰 블록 그룹을 찾는 코드이다. 

앞에 명시한 알고리즘을 다시 보자.

 

1.  크기가 가장 큰 블록 그룹을 찾는다. -> find_block()

• 블록 그룹에는 적어도 하나의 일반 블록이 포함되어야 함 -> 격자(block)을 완전 탐색
• 완전 탐색 중에 일반 블록을 발견 시, 인접한 블록을 탐색하며 블록 그룹을 찾는다. -> BFS
• 정렬 기준에 맞게 가장 큰 블록 그룹 선택

먼저 하단 while문 부분이 격자(block)을 완전 탐색하는 부분에 해당한다.

 

만약 일반 블록을 찾으면, find_block()함수를 호출한다.

 

find_block() 함수에서는 BFS를 통해 검은 블록을 제외하고, 

일반 블록(normals), 무지개 블록(rainbows)로 나누어 저장한다.

 

정렬 기준은 

블록 그룹의 크기 > 무지개 블록의 수 > 기준 블록의 행 > 기존 블록의 열 기준으로 큰 값이다.

 

return문에 정렬 기준에 맞게 값을 반환하도록 작성해주면 간단하다.

 

주의할 점은, 무지개 블록은 다른 블록 그룹을 만들 때 중복 사용될 수 있으므로

BFS가 끝난 후 visited = False 처리도 꼭 해주어야 한다.

 

 

2. 격자에 중력 작용

# 검은색 블록(-1)을 제외한 모든 블록이 아래(down) 방향으로 이동한다.
def gravity():
	for i in range(n-2, -1, -1):
		for j in range(n):
			if block[i][j] != -1:
				pointer = i
				
                # 다음 칸이 격자 끝이거나, 다른 블록이 존재하는 경우 종료
				while pointer + 1 < n and block[pointer + 1][j] == -2:
					block[pointer + 1][j] = block[pointer][j]
					block[pointer][j] = -2
					pointer += 1

해당 코드는 삼성 sw 역량테스트 기출문제 중 2048(EASY) 문제를 풀면서 구현해 본 경험이 있었다.

 

검은색 블록은 중력의 영향을 받지 않으므로 이에 주의해서 코드를 작성하자.

 

 

3. 격자를 90도 반시계 방향으로 회전

# 4. 90' 반시계 방향으로 회전한다.
def rotate_block():
	global block
	
	tmp = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			tmp[n-j-1][i] = block[i][j]

	block = tmp

전체 배열을 회전시키는 문제 역시, 삼성에서 정말정말 좋아하는 유형이다. (배열 돌리기 1로 꼭 연습해보길 권장한다.)

 

배열을 회전시키는 방법은 대표적으로 세 가지가 있다.

 

1. 순수 관계식을 통해 회전 구현(위 코드는 1번 방법을 적용하였다!)

2. deque의 rotate() 메소드 이용

3. transpose 이용하기

 

위 코드는 1번 방법을 적용하여 풀었다!

다른 방법들은 추후에 따로 정리해서 소개할 예정이다 :)

 

 

코드

from collections import deque
import sys

input = sys.stdin.readline

'''
풀이 방법 : 구현 + BFS
시간 복잡도 : 168ms(BOJ 기준)
공간 복잡도 : O(n^2)

1.  크기가 가장 큰 블록 그룹을 찾는다. -> find_block()
- 블록 그룹에는 적어도 하나의 일반 블록이 포함되어야 함 
- 완전 탐색 중에 일반 블록을 발견 시, 인접한 블록을 탐색하며 블록 그룹을 찾는다.
- 정렬 기준에 맞게 가장 큰 블록 그룹 선택

2.  모든 블록 제거
3.  격자에 중력 작용 
4.  격자가 90도 반시계 방향으로 회전
5.  다시 격자에 중력 작용
6.  1~5의 과정 반복

옵션 1.  블록 그룹이 더 이상 존재하지 않으면 획득한 점수 출력  -> 종료 조건

'''

# 1. 크기가 가장 큰 블록을 찾는다.
def find_block(i, j, block_num):
	q = deque()
	q.append((i, j))

	normals = [[i, j]]
	rainbows = []

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

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

			if 0<=nx<n and 0<=ny<n:
				#무지개 블록을 만난 경우
				if block[nx][ny] == 0 and not visited[nx][ny]:
					q.append((nx, ny))
					rainbows.append([nx, ny])
					visited[nx][ny] = 1

				elif block[nx][ny] == block_num and not visited[nx][ny]:
					q.append((nx, ny))
					normals.append([nx, ny])
					visited[nx][ny] = 1

	for x, y in rainbows: # 무지개 블록들은 visited = False 처리
		visited[x][y] = 0

	# 블록 수, 무지개 블록 수, 그룹 내 불록들 위치 정보
	return [len(normals + rainbows), len(rainbows), normals + rainbows]
			
			
# 2. find_block에서 찾은 모든 블록을 제거한다.
def remove_block(group):
	global score

	score += group[0] ** 2

	for x, y in group[2]:
		block[x][y] = -2 # 제거된 블록은 -2로 표시

# 3. 중력이 작용한다.
def gravity():
	for i in range(n-2, -1, -1):
		for j in range(n):
			if block[i][j] != -1:
				pointer = i

				while pointer + 1 < n and block[pointer + 1][j] == -2:
					block[pointer + 1][j] = block[pointer][j]
					block[pointer][j] = -2
					pointer += 1

# 4. 90' 반 시계 방향으로 회전한다.
def rotate_block():
	global block
	
	tmp = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			tmp[n-j-1][i] = block[i][j]

	block = tmp


n, m = map(int, input().rstrip('\n').split())

block = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]

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

score = 0

while True:
	visited = [[0] * n for _ in range(n)]
	groups = []
	
	for i in range(n):
		for j in range(n):
			if block[i][j] >= 1 and not visited[i][j]:
				visited[i][j] = 1
				group = find_block(i, j, block[i][j])

				if group[0] >= 2:
					groups.append(group)

	groups.sort(reverse = True)
	
	if not groups:
		break

	remove_block(groups[0])
	gravity()
	rotate_block()
	gravity()

print(score)

이 문제는 2021년도 상반기 SW역량테스트 오전 문제이다.

 

위 문제는 시간 복잡도를 계산하기 다소 어려웠던 이유는

더 이상 블록 그룹이 없을 때까지 반복하므로

만일 블록 그룹이 최대 개수로 생긴다면, 그만큼 블록 그룹을 탐색하는 BFS의 범위는 줄어들게 되기 때문이다.

 

전반적으로 삼성 기출문제들을 풀다보니, 비슷한 아이디어의 코드들이 자주 등장하는 것을 확인할 수 있었다!!