[백준 21611] 마법사 상어와 블리자드 (Python / 구현)

1. https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

 

다른 사람 풀이를 참고하지 않고 내 힘으로 풀어서 굉장히 뿌듯했던 문제 .. ^^

무려 골1 이였다!! ㅎㅎㅎ

이거 풀 때만해도 삼성코테 뿌시기 가능!! 하면서 자신감이 뿜뿜했는데 .. 항상 조져지는 것은 나였지 ..ㅎ

열심히 연습해서 다음 기회에는 꼭 문제를 풀 수 있었으면!!

 

---

일단 이 문제는 한 문제 지만 약 5문제가 합쳐져 있는 느낌이 들었다.

사고가 어렵게 필요하진 않지만, 시간이 매우 오래 걸렸던 문제

 

문제 이해하기

기본 입력

입력된 배열은 다음과 같다. 배열 정가운데에 "상어"가 있고, 달팽이 방행으로 구슬이 존재한다.

 

1. 마법 공격

다음 그림과 같이 마법 공격을 통해 방향에 대한 벽이 부서질 수도 있다.

 

2. 구슬은 상어를 중심으로 중력 적용

상어를 중심으로 중력이 적용되며 빈칸을 없앤다.

 

3. 구슬의 폭발과 다시 중력 적용(폭발하는 구슬 없을 때까지 무한 반복) LIKE 애니팡~~

구슬이 4개 이상 연속하는 구슬이 있을 때, 구슬이 폭발 하고 채워지고를 반복한다.

이 때 폭발한 구슬을 세줘야 한다

1 * (폭발한 1번 구슬의 개수) + 2 * (폭발한 2번 구슬의 개수) + 3 * (폭발한 3번 구슬의 개수)

 

4. 그룹만들어 재배열

나는 이 부분이 많이 헷갈렸다. 

첫번째처럼 더 이상 폭발하지 않는 구슬 묶음이 만들어 지면, 같은 구슬 번호 당 한 그룹이 된다.

이 때 한 그룹은 [구슬 개수, 구슬 번호] 묶음이 되고 이 묶음을 상어가 있는 곳부터 재배열 한다. 

• 한 그룹 당 무조건 2개
• 그룹은 달팽이길 그대로 적용되는 것이다

• 한 그룹 당 무조건 2개
• 그룹은 달팽이길 그대로 적용되는 것이다

나는 이상하게 문제 읽으면서 헷갈렸다 그냥 BFS로 풀 뻔

 

 

---

 

먼저 문제를 읽고 달팽이 길은 쭉 펼치면 1차원 리스트가 된다.

1차원 리스트에 array 좌표 순서를 기억해주고, 찾는 값은 달팽이 길에서, 실제 값은 array에서 받아오는 식으로 진행했다.

다음과 같이 !!

 

0. 달팽이 길만들어주기

# 달팽이 구하는 방법 - 길 미리 저장
def make_road(array):
	seq_list = []
	# 좌 -> 하 -> 우 -> 상
	dr = [0, 1, 0, -1]
	dc = [-1, 0, 1, 0]
	size = 0
	r, c = x, y

	for idx in range(n * 2 - 1):
		direction = idx % 4  # 방향

		if direction == 0 or direction == 2:
			size += 1

		for _ in range(size):
			nr = r + dr[direction]
			nc = c + dc[direction]
			seq_list.append((r, c))
			r, c = nr, nc

	return seq_list

• 해당 코드는 "[백준 20057] 마법사 상어와 토네이도" 문제를 풀며 달팽이 회전에 대해 이해를 하였다.. !

 

 

1. 마법 공격

# 블리자드 마법 시행
def attack_to_direction(d, s):
	for i in range(1, s + 1):

		# 상하 값이면
		if d == 0 or d == 1:
			move_x = dx[d] * i
			move_y = dy[d]

		else:
			move_x = dx[d]
			move_y = dy[d] * i

		nx = x + move_x
		ny = y + move_y
		# 구슬 공백을 0으로 대체
		array[nx][ny] = 0

	return array

 

2. 구슬은 상어를 중심으로 중력 적용

이 중력 값은 포인터 식으로 해결했다.

@bellejoie_1004 천사 밸리조이님의 1타 강의를 통해 "중력" 문제의 해결 방법을 이해했고, 문제에 적용했다.

중력 문제는 "[백준 21609] 상어 중학교" 에서 이해했다.

@bellejoie_1004 가 알려준대로 그렸다!

다음 원리로 스택을 이용하여, 중력을 구현하였다.

# 벽 파괴 시, 구슬의 이동 결과
def move_to_center():
	empty = 0
	# 반대로 뒤집는 stack
	road_rev = copy.deepcopy(road)
	road_rev.reverse()  # 스택 거꾸로 센다
	# 맨 마지막 스택 부터
	for index in range(len(road_rev) - 1, -1, -1):
		r, c = road_rev[index]
		if array[r][c] == 0:
			empty += 1
		else:
			if index + empty != index:
				# new는 더 앞에 있는 값
				new_r, new_c = road_rev[index + empty]
				array[new_r][new_c] = array[r][c]
				array[r][c] = 0

	return array

 

 

3. 구슬의 폭발과 다시 중력 적용(폭발하는 구슬 없을 때까지 무한 반복) LIKE 애니팡~~

 

4개 이상 연속일 경우 중복인 칸을 제거해주었다.

# 구슬의 폭발 - 투포인터
def distroy_marble():
	dupli = 0 # 중복 검사
	target = array[n//2][n//2]
	distroy_count = 1e9
	while distroy_count > 0:
		distroy_count = 0
		for start in range(len(road)):
			now_x, now_y = road[start] 	# 포인터
			# 중복일 경우 -> 중복인 칸만큼 카운트
			if array[now_x][now_y] == target and array[now_x][now_y] != 0:
				dupli += 1
			# 중복이 아닐 경우
			else:
				# 4개 이상 연속이였을 때
				if dupli >= 4 :
					distroy_count += 1
					# print("dupli : ", dupli)
					# 파괴해야할 묶음(개수)
					for idx in range(dupli):
						distroy_x, distroy_y = road[start-(idx+1)]
						total_result[array[distroy_x][distroy_y]] += 1
						# print(distroy_x, distroy_y, array[distroy_x][distroy_y])
						array[distroy_x][distroy_y] = 0

				# 다시 가던길 간다. dupli, target 초기화
				dupli = 1
				target = array[now_x][now_y]
				# print(f"x : {now_x}, y : {now_y} : target = {array[now_x][now_y]} :dupli : {dupli}")
		move_to_center()
	return array

 

4. 그룹만들어 재배열

 

그룹 만들어주는 함수! 

# group 만들기
def make_group(x,y,target, index, visited):
	group = []
	for idx in range(index, len(road)):
		nx, ny = road[idx]
		if array[nx][ny] == target :
			visited[idx] = 1
			nx, ny = x, y
			group.append((nx, ny))
		else:
			break
	return len(group), target

새로운 배열 만들어 리턴해주는 함수

새로운 배열을 만들어 줄때는, 달팽이 길 stack을 제외한 1차원리스트를 만들어주고, 

group 의 A, B 값 [그룹 길이, 그룹 번호]를 차곡차곡 쌓아줬다. (상어값으로 초기화)

그 이후, 빈 칸에 대해 0을 대체해주었다.

달팽이 길 stack (Array의 좌표 번호를 나타냄)과 1차원 리스트 (새로 만들어줄 배열 값 리스트) 를 1:1로 매칭하여, 

새로운 Array의 구슬 번호를 입력해주었다.

 

실행

import copy
from collections import deque

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
x, y = n // 2, n // 2
array[x][y] = -1

# 1,2,3,4 (direction 값은 -1 씩 해줘야 함)
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

total_result = {
	1 : 0,
	2 : 0,
	3 : 0
}

# 새로운 array 만들기
road = make_road(array)	# 정방형

for _ in range(m):
	distroy_cnt = 0
	d, s = map(int, input().split())
	attack_to_direction(d - 1, s)
	move_to_center()	# 구슬 가운데로 모으기
	distroy_marble()	# 구슬 4보다 큰 중복값 없을 때까지 반복
	array = new_array()

# print("final :: ", array)
answer = 0
for key, value in total_result.items():
	answer += key*value

print(answer)

 

---

나의 코드

# 21611번 - 마법사 상어와 블리자드
import copy
from collections import deque

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
x, y = n // 2, n // 2
array[x][y] = -1

# 1,2,3,4 (direction 값은 -1 씩 해줘야 함)
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

total_result = {
	1 : 0,
	2 : 0,
	3 : 0
}

# 달팽이 구하는 방법 - 길 미리 저장
def make_road(array):
	seq_list = []
	# 좌 -> 하 -> 우 -> 상
	dr = [0, 1, 0, -1]
	dc = [-1, 0, 1, 0]
	size = 0
	r, c = x, y

	for idx in range(n * 2 - 1):
		direction = idx % 4  # 방향

		if direction == 0 or direction == 2:
			size += 1

		for _ in range(size):
			nr = r + dr[direction]
			nc = c + dc[direction]
			seq_list.append((r, c))
			r, c = nr, nc

	return seq_list

# 블리자드 마법 시행
def attack_to_direction(d, s):
	for i in range(1, s + 1):

		# 상하 값이면
		if d == 0 or d == 1:
			move_x = dx[d] * i
			move_y = dy[d]

		else:
			move_x = dx[d]
			move_y = dy[d] * i

		nx = x + move_x
		ny = y + move_y
		# 구슬 공백을 0으로 대체
		array[nx][ny] = 0

	return array

# 벽 파괴 시, 구슬의 이동 결과
def move_to_center():
	empty = 0
	# 반대로 뒤집는 stack
	road_rev = copy.deepcopy(road)
	road_rev.reverse()  # 스택 거꾸로 센다
	# 맨 마지막 스택 부터
	for index in range(len(road_rev) - 1, -1, -1):
		r, c = road_rev[index]
		if array[r][c] == 0:
			empty += 1
		else:
			if index + empty != index:
				# new는 더 앞에 있는 값
				new_r, new_c = road_rev[index + empty]
				array[new_r][new_c] = array[r][c]
				array[r][c] = 0

	return array

# 구슬의 폭발 - 투포인터
def distroy_marble():
	dupli = 0 # 중복 검사
	target = array[n//2][n//2]
	distroy_count = 1e9
	while distroy_count > 0:
		distroy_count = 0
		for start in range(len(road)):
			now_x, now_y = road[start] 	# 포인터
			# 중복일 경우 -> 중복인 칸만큼 카운트
			if array[now_x][now_y] == target and array[now_x][now_y] != 0:
				dupli += 1
			# 중복이 아닐 경우
			else:
				# 4개 이상 연속이였을 때
				if dupli >= 4 :
					distroy_count += 1
					# print("dupli : ", dupli)
					# 파괴해야할 묶음(개수)
					for idx in range(dupli):
						distroy_x, distroy_y = road[start-(idx+1)]
						total_result[array[distroy_x][distroy_y]] += 1
						# print(distroy_x, distroy_y, array[distroy_x][distroy_y])
						array[distroy_x][distroy_y] = 0

				# 다시 가던길 간다. dupli, target 초기화
				dupli = 1
				target = array[now_x][now_y]
				# print(f"x : {now_x}, y : {now_y} : target = {array[now_x][now_y]} :dupli : {dupli}")
		move_to_center()
	return array

# group 만들기
def make_group(x,y,target, index, visited):
	group = []
	for idx in range(index, len(road)):
		nx, ny = road[idx]
		if array[nx][ny] == target :
			visited[idx] = 1
			nx, ny = x, y
			group.append((nx, ny))
		else:
			break
	return len(group), target

# 새로운 array 만들기
def new_array():
	new_array = [[0]*n for _ in range(n)]
	target_road = [-1]
	visited = [0]*len(road)
	# 새로운 배열 만들기!!

	for index in range(1,len(road)):
		i, j = road[index]
		if array[i][j] != 0 and visited[index] == 0:
			len_group, marble_num = make_group(i,j, array[i][j], index, visited)
			target_road.append(len_group)
			target_road.append(marble_num)
			# print(len_group, marble_num)
	target_road = target_road + [0]*(len(road)-len(target_road))

	for index in range(len(road)):
		x, y = road[index]
		new_array[x][y] = target_road[index]

	return new_array

road = make_road(array)	# 정방형

for _ in range(m):
	distroy_cnt = 0
	d, s = map(int, input().split())
	attack_to_direction(d - 1, s)
	move_to_center()	# 구슬 가운데로 모으기
	distroy_marble()	# 구슬 4보다 큰 중복값 없을 때까지 반복
	array = new_array()

# print("final :: ", array)
answer = 0
for key, value in total_result.items():
	answer += key*value

print(answer)

 

한 문제에 많은 개념이 들어가 있어, 풀이 시간이 오래 걸렸다 .. 6시간 정도 ..?

이것도 익숙해지면, 구현할 수 있는 범위가 넓어질 것 같다!

 

그냥 뿌듯함에 오랜만에 알고리즘 풀이 정리 끝!