https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
문제
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이며 마법사 상어는 ((N+1)/2, (N+1)/2)에 있다.
일부 칸과 칸 사이에는 벽이 세워져 있으며, 다음은 N = 3, 5, 7인 경우의 예시이다. 실선은 벽이고, 점선은 벽이 아니다. 칸에 적혀있는 수는 칸의 번호이다.
가장 처음에 상어가 있는 칸을 제외한 나머지 칸에는 구슬이 하나 들어갈 수 있다. 구슬은 1번 구슬, 2번 구슬, 3번 구슬이 있다. 같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면, 그 구슬을 연속하는 구슬이라고 한다.
블리자드 마법을 시전하려면 방향 di와 거리 si를 정해야 한다. 총 4가지 방향 ↑, ↓, ←, →가 있고, 정수 1, 2, 3, 4로 나타낸다. 상어는 di 방향으로 거리가 si 이하인 모든 칸에 얼음 파편을 던져 그 칸에 있는 구슬을 모두 파괴한다. 구슬이 파괴되면 그 칸은 구슬이 들어있지 않은 빈 칸이 된다. 얼음 파편은 벽의 위로 떨어지기 때문에, 벽은 파괴되지 않는다.
다음 예시는 방향은 아래, 거리는 2인 경우이다.
만약 어떤 칸 A의 번호보다 번호가 하나 작은 칸이 빈 칸이면, A에 있는 구슬은 그 빈 칸으로 이동한다. 이 이동은 더 이상 구슬이 이동하지 않을 때까지 반복된다. 따라서, 구슬이 파괴된 후에는 빈 칸이 생겨 구슬이 이동하고, 구슬이 모두 이동한 결과는 다음과 같다.
이제 구슬이 폭발하는 단계이다. 폭발하는 구슬은 4개 이상 연속하는 구슬이 있을 때 발생한다. 다음은 왼쪽 그림은 위의 상태에서 폭발하는 구슬이 들어있는 칸을 파란색과 초록색으로 표시한 것이고, 오른쪽 그림은 구슬이 폭발한 후의 상태이다.
위의 상태는 4개 이상 연속하는 구슬이 있기 때문에 구슬이 다시 폭발하게 된다.
이제 더 이상 폭발한 구슬이 없기 때문에, 구슬이 변화하는 단계가 된다. 연속하는 구슬은 하나의 그룹이라고 한다. 다음은 1번 구슬은 빨간색, 2번 구슬은 파란색, 3번 구슬은 보라색으로 표시한 그림이다.
하나의 그룹은 두 개의 구슬 A와 B로 변한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호이다. 구슬은 다시 그룹의 순서대로 1번 칸부터 차례대로 A, B의 순서로 칸에 들어간다. 다음 그림은 구슬이 변화한 후이고, 색은 구분하기 위해 위의 그림에 있는 그룹의 색을 그대로 사용했다. 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.
마법사 상어는 블리자드를 총 M번 시전했다. 시전한 마법의 정보가 주어졌을 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구해보자.
입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.
다음 M개의 줄에는 블리자드 마법의 방향 di와 거리 si가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.
출력
첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.
제한
- 3 ≤ N ≤ 49
- N은 홀수
- 1 ≤ M ≤ 100
- 1 ≤ di ≤ 4
- 1 ≤ si ≤ (N-1)/2
- 칸에 들어있는 구슬이 K개라면, 구슬이 들어있는 칸의 번호는 1번부터 K번까지이다.
- 입력으로 주어진 격자에는 4개 이상 연속하는 구슬이 없다.
풀이
대박적으로 할일이 많고 머리가 아팠다... 마법사 상어는 쉬지도 않고 뭘 배워오네..
구슬이 이동하는 폼이 마법사 상어와 토네이도(https://harami.tistory.com/42)가 생각이 났다. 비슷하게 해보고 싶은데 너문무 복잡해지는걸 느끼면서 다른 풀이를 찾아봤다.
구슬이 움직이는 방향은 정해져 있으면서 계속해서 이동을 해야한다. 이동하는 방향이 정해져 있기 때문에 토네이도처럼 생긴 좌표를 새로운 좌표로 저장한다. 마치 (x, y)좌표를 (cos, sin)으로 변환하는 것처럼...
전체적인 루틴을 간단히 표현하면 다음과 같다.
해야할 일들을 세분화 해서 함수로 정리하면 다음과 같다.
- 새로운 좌표로 인덱싱
- 구슬 파편 던지기
- 빈칸으로 구슬 이동
- 구슬 폭발
- 구슬 변화
인덱싱(indexing)
토네이도 때와 마찬가지로 [좌, 하], [우, 상]이 짝으로 방향회전을 한다. 움직이는 칸의 개수는 쌍이 동일하며 하나의 쌍을 지나면서 1씩 증가하게 된다. 새로운 x,y는 리스트를 이용하여 순서대로 보관한다.
def indexing():
x, y = n//2, n//2
# 움직이는 칸의 수
move = 0
# 좌, 하, 우, 상
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
while True:
# 4방향으로 회전
for i in range(4):
# (좌/하), (우,상) 이후 방향 회전
if i % 2 == 0:
move += 1
for _ in range(move):
x = x + dx[i]
y = y + dy[i]
tornado.append([x, y])
if x == 0 and y == 0:
return len(tornado)
빈칸 채우기(fill_blank)
큐를 이용해서 맵에 남은 구슬 저장한다. 이후, 새로운 좌표를 순서대로 구슬을 채워넣는다. 모든 빈칸을 채운 후, 나머지 공간은 빈칸으로 놔둔다.
def fill_blank():
beads = deque()
for x, y in tornado:
if game_map[x][y]:
beads.append(game_map[x][y])
for x, y in tornado:
if beads:
game_map[x][y] = beads.popleft()
else:
game_map[x][y] = 0
구슬 폭발(bomb_beads)
연속으로 4개의 구슬이 되는 그룹을 찾는다. 폭발한 구슬의 개수를 저장.
구슬의 폭발은 연속된 4개의 구슬이 없을 때까지 반복해야 하므로, check라는 플래그를 이용해 폭발 수행여부를 저장한다.
def bomb_beads():
check = False
value, cnt = game_map[tornado[0][0]][tornado[0][1]], 1
bomb = [tornado[0]]
for idx in range(1, length):
if value != game_map[tornado[idx][0]][tornado[idx][1]]:
if value and cnt >= 4:
check = True
result[value-1] += cnt
for x, y in bomb:
game_map[x][y] = 0
# 구슬 색이 다르지만 4개 이하일 경우 리셋
value = game_map[tornado[idx][0]][tornado[idx][1]]
bomb = []
cnt = 0
bomb.append(tornado[idx])
cnt += 1
# 마지막 구슬 까지 확인했을 때
if value and cnt >= 4:
check = True
result[value-1] += cnt
for x, y in bomb:
game_map[x][y] = 0
return check구슬 변화(new_beads)
연속된 구슬 그룹을 찾는다. 그룹을 이루는 구슬의 개수와 번호를 순서대로 저장한다.
저장이 완료되면, 새롭게 구슬 맵을 구성한다.
def new_beads():
value, cnt = game_map[tornado[0][0]][tornado[0][1]], 1
temp = deque()
for idx in range(1, length):
# 다음 구슬의 색이 다른 경우
if game_map[tornado[idx][0]][tornado[idx][1]] != value:
# 구슬 개수, 구슬 번호 순으로 저장
temp.append(cnt)
temp.append(value)
# 새로운 구슬 색 저장
value = game_map[tornado[idx][0]][tornado[idx][1]]
cnt = 0
# 다음 구슬 색이 같은 경우 숫자 +1
cnt += 1
# 마지막 구슬까지 확인 후, 변화
if value:
temp.append(cnt)
temp.append(value)
# 새로운 구슬 맵 구성
for x, y in tornado:
if temp:
game_map[x][y] = temp.popleft()
else:
game_map[x][y] = 0
코드
from collections import deque
n, m = map(int, input().split())
game_map = [list(map(int,input().split())) for _ in range(n)]
magic_list = [list(map(int, input().split())) for _ in range(m)]
shark = [n//2, n//2]
tornado = []
def indexing():
x, y = n//2, n//2
# 움직이는 칸의 수
move = 0
# 좌, 하, 우, 상
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
while True:
# 4방향으로 회전
for i in range(4):
# (좌/하), (우,상) 이후 방향 회전
if i % 2 == 0:
move += 1
for _ in range(move):
x = x + dx[i]
y = y + dy[i]
tornado.append([x, y])
if x == 0 and y == 0:
return len(tornado)
length = indexing()
result = [0, 0, 0]
def fill_blank():
beads = deque()
for x, y in tornado:
if game_map[x][y]:
beads.append(game_map[x][y])
for x, y in tornado:
if beads:
game_map[x][y] = beads.popleft()
else:
game_map[x][y] = 0
def bomb_beads():
check = False
value, cnt = game_map[tornado[0][0]][tornado[0][1]], 1
bomb = [tornado[0]]
for idx in range(1, length):
if value != game_map[tornado[idx][0]][tornado[idx][1]]:
if value and cnt >= 4:
check = True
result[value-1] += cnt
for x, y in bomb:
game_map[x][y] = 0
# 구슬 색이 다르지만 4개 이하일 경우 리셋
value = game_map[tornado[idx][0]][tornado[idx][1]]
bomb = []
cnt = 0
bomb.append(tornado[idx])
cnt += 1
# 마지막 구슬 까지 확인했을 때
if value and cnt >= 4:
check = True
result[value-1] += cnt
for x, y in bomb:
game_map[x][y] = 0
return check
def new_beads():
value, cnt = game_map[tornado[0][0]][tornado[0][1]], 1
temp = deque()
for idx in range(1, length):
# 다음 구슬의 색이 다른 경우
if game_map[tornado[idx][0]][tornado[idx][1]] != value:
# 구슬 개수, 구슬 번호 순으로 저장
temp.append(cnt)
temp.append(value)
# 새로운 구슬 색 저장
value = game_map[tornado[idx][0]][tornado[idx][1]]
cnt = 0
# 다음 구슬 색이 같은 경우 숫자 +1
cnt += 1
# 마지막 구슬까지 확인 후, 변화
if value:
temp.append(cnt)
temp.append(value)
# 새로운 구슬 맵 구성
for x, y in tornado:
if temp:
game_map[x][y] = temp.popleft()
else:
game_map[x][y] = 0
# 상/하/좌/우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for d, s in magic_list:
# 파편 던지기
for i in range(1, s+1):
x = shark[0] + dx[d-1] * i
y = shark[1] + dy[d-1] * i
game_map[x][y] = 0
# 빈칸 채우기
fill_blank()
# 구슬 폭발
while True:
if bomb_beads():
fill_blank()
else:
break
# 구슬 변화
new_beads()
total = 0
for i in range(3):
total += result[i]*(i+1)
print(total)
'프로그래밍 > Python' 카테고리의 다른 글
| [코드트리] 포탑 부수기 / 파이썬(Python) (0) | 2023.11.02 |
|---|---|
| [백준] 233288번 / 주사위 굴리기 2 / 파이썬(Python) (1) | 2023.10.30 |
| [백준] 21610번 / 마법사 상어와 비바라기 / 파이썬(Python) (0) | 2023.10.26 |
| [백준] 21608번 / 상어초등학교 / 파이썬(Python) (1) | 2023.10.26 |
| [백준] 20058번 / 마법사 상어와 파이어스톰 / 파이썬(Python) (0) | 2023.10.26 |
댓글