21609: 상어 중학교

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

21609번: 상어 중학교

설명

이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.

블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득한다.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다. 오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

핵심 아이디어

1. 오토플레이 -> whilte 문 활용
2. 크기가 가장 큰 블록 찾기 -> BFS 활용, 이들 중 크기 > 무지개 블록의 수 > 기준 블록의 행 > 기준 블록의 열 
3. 중력 함수 구현
4. 90도 반시계 방향 회전 함수 구현

---

1. 크기가 가장 큰 블록 그룹을 찾는다. -> BFS 함수 정의
   • 블록 그룹에는 적어도 하나의 일반 블록이 포함되어야 함
   • 완전 탐색 중에 일반 블록을 발견 시, 인접한 블록을 탐색하며 블록 그룹을 찾는다. 
   • 정렬 기준에 맞게 가장 큰 블록 그룹 선택.
2. 모든 블록 제거
3. 격자에 중력 작용
4. 격자가 90도 반시계 방향으로 회전
5. 다시 격자에 중력 작용
6. 1~5의 과정을 반복

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

코드 구현

from collections import deque
import sys
input = sys.stdin.readline

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

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

	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):
				# 무지개 블록을 만난 경우 : rainbow에 추가
				if graph[nx][ny] == 0 and not visited[nx][ny]:
					q.append((nx,ny))
					rainbows.append([nx,ny])
					visited[nx][ny] = True
				# 일반 블록을 만난 경우
				elif graph[nx][ny] == block_num and not visited[nx][ny]:
					q.append((nx,ny))
					normals.append([nx,ny])
					visited[nx][ny] = True
	# 무지개 블록은 다른 블록 그룹을 만들 때 중복 사용될 수 있기 때문
	# 에 BFS가 끝난 후 visited = False 해줘야한다.
	for x,y in rainbows:
		visited[x][y] = False
	# 정렬 기준에 맞게 return : 블록 수,  무지개 블록 수, 그룹 내 블록들 위치 정보(행, 열)
	return [len(normals+rainbows), len(rainbows), normals + rainbows]

# 2. bfs에서 찾은 모든 블록을 제거한다.
score = 0
def remove(group):
	global score

	score += group[0] ** 2
	for x,y in group[2]:
		graph[x][y] = -2 # 제거된 블록은 -2로 표시

# 격자에 중력 작용, 검은색 블록은 중력의 영향을 받지 않는 것에 주의
# 즉, 검색은 블록(-1)을 제외한 모든 블록이 아래(down) 방향으로 이동한다.
# 3. 중력작용
def gravity():
	for i in range(n-2,-1,-1): # 밑에서 부터 체크
		for j in range(n):
			if graph[i][j] != -1: # -1이 아니면 아래로 다운
				pointer = i
				# 다음 행이 인덱스 범위 안이면서 -2면 아래로 다운
				while pointer + 1 < n and graph[pointer+1][j] == -2:
					graph[pointer+1][j] = graph[pointer][j]
					graph[pointer][j] = -2
					pointer += 1
# 90도 반시계 방향으로 회전
def rotate():
	global graph
	temp = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			# 시계 방향이 아니라 반시계 방향으로 회전
			temp[n-j-1][i] = graph[i][j]
	graph = temp


# 격자 크기, 색상의 개수
n, m = map(int, input().split())
# 격자 정보 입력받기
graph = [list(map(int, input().split())) for _ in range(n)]
# 인접칸 이동을 위한 방향 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 조건에 맞게 실행
while True:
	visited = [[False] * n for _ in range(n)] # 방문 여부 표시
	groups = [] # 블록 그룹 저장

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

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

	if not groups:
		break # 종료 조건
	# 2. 블록 제거하기
	remove(groups[0])
	# 3. 중력 작용
	gravity()
	# 4. 격자 회전
	rotate()
	# 5. 다시 중력 작용
	gravity()

print(score)

1. 크기가 가장 큰 블록 그룹을 찾는다. -> bfs(i,j,block_num)

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

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

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

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

 

해당 부분이 격자를 완전 탐색하는 코드 부분이다. 완전 탐색 도중 일반 블록을 찾으면 BFS 함수를 호출한다. 

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

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

	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):
				# 무지개 블록을 만난 경우 : rainbow에 추가
				if graph[nx][ny] == 0 and not visited[nx][ny]:
					q.append((nx,ny))
					rainbows.append([nx,ny])
					visited[nx][ny] = True
				# 일반 블록을 만난 경우
				elif graph[nx][ny] == block_num and not visited[nx][ny]:
					q.append((nx,ny))
					normals.append([nx,ny])
					visited[nx][ny] = True
	# 무지개 블록은 다른 블록 그룹을 만들 때 중복 사용될 수 있기 때문
	# 에 BFS가 끝난 후 visited = False 해줘야한다.
	for x,y in rainbows:
		visited[x][y] = False
	# 정렬 기준에 맞게 return : 블록 수,  무지개 블록 수, 그룹 내 블록들 위치 정보(행, 열)
	return [len(normals+rainbows), len(rainbows), normals + rainbows]

BFS 함수에서는 검은 블록은 제외하고 일반 블록과 무지개 블록으로 나누어 저장한다. 정렬 기준은

 크기 > 무지개 블록의 수 > 기준 블록의 행 > 기준 블록의 열  기준으로 큰 값이다. 이때, return 문제 정렬 기준에 맞게 값을 반환하도록 작성하면 편리하다. 그리고 주의할 점은 무지개 블록은 다른 블록 그룹을 만들 때 중복 사용 될 수 있으므로 BFS가 끝난 후에는 다시 visited = False 로 만들어 주어야 한다. 

 

2. 격자에 중력 작용

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

중력작용은 삼성 기출문제 2048(EASY) 문제에도 적용 된다.

 

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

# 90도 반시계 방향으로 회전
def rotate():
	global graph
	temp = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			# 시계 방향이 아니라 반시계 방향으로 회전
			temp[n-j-1][i] = graph[i][j]
	graph = temp

 

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

참고 블로그

https://youwjune.tistory.com/14

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

 

https://jennnn.tistory.com/68

[백준] 21609. 상어 중학교 / python 파이썬