문제
https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
풀이
문제의 기능들을 본격적으로 구현하기전에, 회오리 방향으로 2차원 배열에 쉽게 접근하는 방식을 구현하고 싶었다.
| (0,0) | (0,1) | (0,2) |
| (1,0) | (1,1) | (1,2) |
| (2,0) | (2,1) | (2,2) |
무슨 말이냐면, 위와같이 3*3 배열이 있을때 0이라는 키는 (1,1) 좌표를 뱉고, 1은 (1,0), 2는 (2,0) 이라는 좌표를 뱉는 딕셔너리를 구현하고 싶었다. 해당 자료구조만 있다면 순차적으로 접근하면서 로직 처리가 굉장히 간편해질 거 같았기 때문이다. 마법사 상어와 토네이도 에서 토네이도 모양으로 접근했기 때문에, 이 때 기억을 되살려서 처리했다. 정확히는 토네이도 문제를 자의적으로 풀고, 다른 코드를 참고해서 알아낸 방법이다.
가장 중앙을 기준으로 좌,하,우,상 을 반복적으로 접근하게 된다.
행의 인덱스가 짝수일때만 [좌,하]를 수행하고, 홀수일때는 [우,상]을 수행한다. 횟수 같은 경우에는 [좌,하]는 홀수번만큼 접근하고 [우,상]은 짝수번만큼 접근한다. (해당 설명은 코드를 보는게 더 이해가 빠른 거 같다..)
이 특징을 잘 살려서 순차적으로 접근하고, 접근하면서 딕셔너리 값도 초기화 해주면 원하는 자료구조를 만들 수 있다.
이후에는 4개의 스텝에 따라서 로직을 작성하면 된다.
기본적으로 나는 2차원 배열을 선언해서 입력 받았고, 존재하는 구슬의 총 개수를 저장해두면서 어디가 구슬의 끝인지 기억해두었다.
1. 블리자드
해당 로직은 간단하다. 원점을 기준으로 방향만큼 구슬을 파괴해주면 된다. (0으로 만들기)
주의할점은, 0일 경우에는 파괴하지 않는것이다. 나의 풀이 같은 경우에는 현재 구슬 개수를 항상 카운터하고 활용했기에 0인 경우에는 구슬개수가 차감되면 안됐다.
2. 빈칸 당기기
미리 선언해둔 인덱스로 좌표에 접근하는 딕셔너리를 이 때 사용한다. 딕셔너리 키 를 1부터 최대 구슬개수 까지 접근하면서 해당칸이 비어있는지 확인한다. (이 때 최대 구슬개수는 1에서 파괴한 구슬을 차감하지 않은 상태임을 유의하자.)
비어있다면 가장 가까운 값을 현재칸으로 옮겨주고, 해당칸은 0으로 비워준다. 이 과정을 계속 반복하면 된다.
1에서 파괴한 구슬은 이 과정이 끝나면 총 구슬개수에서 차감해주면 된다. 만약 미리 차감해둔다면 범위에서 오류가 날 수 있기 때문이다.
3. 4개이상 연속된 구슬 폭발
이 로직또한 딕셔너리 키 1부터 최대 구슬개수까지 접근하면서 칸의 값을 확인하면 된다.
구슬의 번호를 반복적으로 확인하면서, 같다면 연속된 횟수를 저장해준다. 만약 다르다면 반복문을 빠져나오고, 연속 횟수가 4회 이상이면 저장해둔 구슬들을 모두 폭발시켜주면 된다. 그 후에 최대 구슬개수까지 계속 반복하면 된다.
만약 그런식으로 한 사이클을 돌았는데 폭발된 구슬이 없다면 다음 단계로 넘어가면 된다.
폭발된게 있다면 2번에서 정의한 당기는 로직을 사용해서 배열을 재구성 한 다음 반복하면 된다.
4. 구슬 변화
사실상 새 배열을 만들어야 하므로 새 배열을 선언한다.
그리고 3번에서 수행했던 방식과 비슷하게 연속된 수의 개수를 체크하고, 번호를 체크해서 새 배열에 넣어주면 된다.
기존 배열의 인덱스와 새롭게 넣어줄 배열의 인덱스를 각각 기억해서 따로 처리해주면 된다.
단 새로운 배열이 꽉 찬 경우에는 구슬을 저장하지 않고 날린다.
어려웠던 점
- 범위검사
- 2차원 배열이고 총 구슬 개수로 끝을 항상 판단했다. 중간중간 코드를 작성하면서 헷갈려서 >= 인지, > 인지 .. 특정 변수로 범위검사하면서 맞는지.. 여러모로 많이 헷갈렸다. 처음 정의를 잘해야지 이런 곤혹을 겪지 않을 거 같다.
- 그냥 범위 검사를 항상 잘해야한다.
- 구슬 파괴
- 위에서도 언급했지만 총 구슬개수로 구슬의 끝을 판단했기에 0인 경우에는 구슬이 파괴되는것을 카운트하면 안된다.
- 구슬이 변화되는 경우에 2차원 배열의 범위를 넘어서면 추가하지 않는다.
- 나는 처음에 2개를 항상 세트로 추가했다. 그러니까 구슬의 개수, 구슬의 번호 두 가지 항목을 한번에 추가했다. 그러나 둘 중 하나만 채우고, 배열이 꽉 찰 수도 있다는 것을 나중에 깨닫고 수정하게 됐다.
코드
import copy
from sys import stdin
def initPosition():
for i in range(n):
if i % 2 == 0:
setPosition(i, 0, -1)
setPosition(i, 1, 0)
else:
setPosition(i, 0, 1)
setPosition(i, -1, 0)
def setPosition(cnt, tx, ty):
global x, y, n, position, idx
for _ in range(cnt + 1):
x += tx
y += ty
if x < 0 or y < 0: break
position[idx] = [x, y]
idx+=1
def increaseExplosionMarble(value):
global breakOne, breakTwo, breakThree
if value == 1: breakOne += 1
if value == 2: breakTwo += 1
if value == 3: breakThree += 1
def getTotalMarble():
global board
temp = 0
for b in board:
for v in b:
if v != 0: temp += 1
return temp
def magicBreak(direction, distance):
global board, n, totalMarble
x = y = n // 2
breakMarbles = 0
# 마법으로 구슬을 파괴한다.
for i in range(distance):
nx = x + dx[direction]
ny = y + dy[direction]
# 범위 안에 들어간다면, 구슬을 파괴한다.
if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
board[nx][ny] = 0
breakMarbles += 1
x = nx
y = ny
else:
break
return breakMarbles
def readjustBoard():
global totalMarble, board, position
targetIdx = 1
for i in range(1, totalMarble):
x = position[i][0]
y = position[i][1]
# 해당 칸이 비어있다면
if board[x][y] == 0:
tx = ty = 0
# 값이 있는위치를 찾는다.
while True:
if targetIdx <= i:
targetIdx += 1
continue
if targetIdx > totalMarble: break
tx = position[targetIdx][0]
ty = position[targetIdx][1]
if board[tx][ty] != 0: break
targetIdx += 1
if targetIdx <= totalMarble:
board[x][y] = board[tx][ty]
board[tx][ty] = 0
def explosionMarble():
global board, position, n, totalMarble
while True:
# 1번째부터 시작한다.
baseIdx = 1
breakMarbles = 0
# 부숴짐이 있었는지 체크한다.
# 한 사이클을 돈다.
while True:
if baseIdx > totalMarble: break
continuous = 0
savedPosition = []
marbleNum = board[position[baseIdx][0]][position[baseIdx][1]]
# 같은 값을 모두 체크한다.
while True:
if baseIdx > totalMarble: break
if marbleNum == board[position[baseIdx][0]][position[baseIdx][1]]:
continuous += 1
savedPosition.append([position[baseIdx][0], position[baseIdx][1]])
baseIdx += 1
else:
break
# 4개 이상이라면 모두 파괴해준다.
if continuous >= 4:
for _ in range(continuous) : increaseExplosionMarble(marbleNum)
for ox, oy in savedPosition: board[ox][oy] = 0
breakMarbles += continuous
if breakMarbles == 0: break
# 부서진게 있다면 재조정을 해주고 다시 사이클을 돈다.
readjustBoard()
totalMarble -= breakMarbles
def remakeBoard():
global totalMarble, board, position, n
tempBoard = [[0] * n for _ in range(n)]
originIdx = 1
tempIdx = 1
while True:
if originIdx > totalMarble: break
if tempIdx >= n**2: break
continuous = 0
marbleNum = board[position[originIdx][0]][position[originIdx][1]]
while True:
if originIdx > totalMarble: break
if marbleNum == board[position[originIdx][0]][position[originIdx][1]]:
continuous += 1
originIdx += 1
else:
break
tempBoard[position[tempIdx][0]][position[tempIdx][1]] = continuous
tempIdx += 1
if tempIdx >= n**2: break
tempBoard[position[tempIdx][0]][position[tempIdx][1]] = marbleNum
tempIdx += 1
board = copy.deepcopy(tempBoard)
totalMarble = getTotalMarble()
dx = [-1, -1, 1, 0, 0]
dy = [-1, 0, 0, -1, 1]
position = {}
n, m = map(int, input().split())
board = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
magics = [list(map(int, stdin.readline().rstrip().split())) for _ in range(m)]
idx = 0
x = y = n//2
position[idx] = [x, y]
idx+=1
initPosition()
totalMarble = getTotalMarble()
breakOne = 0
breakTwo = 0
breakThree = 0
for magic in magics:
direction = magic[0]
distance = magic[1]
# 1. 마법으로 구슬을 부순다.
breakMables = magicBreak(direction, distance)
# 2. 당겨온다.
readjustBoard()
totalMarble -= breakMables
# 3. 4개씩 부수는 과정을 반복한다.
explosionMarble()
# 4. 새로운 배열을 구성한다.
remakeBoard()
print(breakOne + (breakTwo * 2) + (breakThree * 3))
후기
구현은 나름 깔끔하게 해서 만족했는데 규모가 워낙 크다보니 반례 찾기가 정말 힘들었다. 다행스럽게 질문탭에서 다 찾았으나, 실전이라면 정말 끔찍하다. ㅠㅠ
'백준' 카테고리의 다른 글
| 13335 - 트럭 (Java) (0) | 2024.08.10 |
|---|---|
| 23290 - 마법사 상어와 복제 (0) | 2023.08.11 |
| 23288 - 주사위 굴리기 2 (0) | 2023.08.08 |
| 19238 - 스타트 택시 (0) | 2023.08.08 |
| 21610 - 마법사 상어와 비바라기 (0) | 2023.07.07 |