문제 요구사항
- 왼쪽, 오른쪽 번갈아가면서 작대기를 던지는 데 던질 때 먼저 닿는 미네랄은 부서짐
- 미네랄이 부서지면서 바닥과 연결된 미네랄과 연결이 끊길 경우 중력의 영향을 받아서 떨어짐
- 단, 떨어질 때 형태가 변하지 않음
해당 문제에서 내가 봤을 때 가장 중요한 포인트는 중력의 영향을 받는 조건이라고 생각한다. 아래는 떨어지는 조건을 보기좋게 정리하였다.
미네랄이 바닥부터 연결되있지 않으면 떨어진다. -> 미네랄의 어떤 부분을 부셨을 때 덩어리 별로 조사하고 해당 덩어리가 바닥과 연결되있지 않으면 떨어진다.
이와 같은 개념을 통해 문제를 접근하면 더욱더 쉬울 것이다.
문제 해결
문제 해결을 위해 아래와 같이 순서를 정하여 코드를 구성하였다.
- 미네랄 파괴 메서드
- 미네랄 덩어리 확인 메서드
- 미네랄 추락 메서드
미네랄 파괴 메서드
우선, 왼쪽 오른쪽 번갈아가면서 작대기를 던질 것이다. 그럼으로 아래의 메서드와 같이 불룬타입 변수를 통해 스위칭하면서 미네랄을 파괴하였다. 그리고 미네랄을 파괴할 때 나중에 중력의 영향을 생각하기 위해 파괴된 부분 근접의 위치를 반환하였다.
원래 미네랄을 파괴하고 전체를 탐색하려고 하였지만 시간 제한조건에 걸릴것같아 진작에 포기하고 필수인 부분만 보기로 하였다.
어떤 미네랄을 파괴했을 때, 중력의 영향을 받을수도 있을 것이다. 그럼 중력의 영향을 받기 위한 조건 중 하나인 미네랄의 연결부분을 파괴했을 때이다. 연결된 부분을 파괴했을 때 파괴된 부분의 군접 위치만 보면 두 덩어리의 시작 위치를 알 수 있을 것이다. 그럼으로 직접 0부터 r,c까지 확인을 안해도 된다.
def throwStick(throwHeight, isLeftThrow):
crashPosX = 0
checkPosList = []
if isLeftThrow:
for i in range(c):
if board[throwHeight][i] == 'x':
board[throwHeight][i] = '.'
crashPosX = i
break
else:
for i in range(c - 1, -1, -1):
if board[throwHeight][i] == 'x':
board[throwHeight][i] = '.'
crashPosX = i
break
# 전체를 보는 것보다 한 묶음 단위로 보면 편하기 때문에
# 어떤 미네랄을 파괴했을 때, 중력으로 떨어지는 부분을 생각할 때 부서진 부분에 근접한 부분만 봐도 됨
# 예시) 어떤 미네랄을 파괴했을 때 중력에 영향을 받을 조건을 달성하기 위해서
# 그 부분이 미네랄과의 연결을 끊을 수 있는 부분이여야 함, 즉 파괴된 부분의 근접한 부분을
# 탐색해서 중력에 영향을 받을 수 있는지 조건을 따지면 전체를 탐색안해도 됨
for i in range(4):
nextX, nextY = crashPosX + controlX[i], throwHeight + controlY[i]
if -1 < nextX < c and -1 < nextY < r:
if board[nextY][nextX] == 'x':
checkPosList.append([nextX, nextY])
return checkPosList미네랄 덩어리 확인 메서드
미네랄 덩어리 확인 및 덩어리끼리 차별을 두기 위해 아래와 같이 BFS를 사용하여 덩어리를 구분하였다. 여기서 주요하게 볼 점은 우리가 덩어리를 나눠 생각할때 중력에 영향을 받을 수 있는지 아닌지 구분해야하는 것이다.
어떤 시작 위치를 기준으로 미네랄을 탐색할 때 만약 현재 탐색의 위치가 바닥에 위치한다면 그 미네랄은 절대 떨어지지 않을 것이다. 왜냐하면 중력의 영향을 받는 조건 중 하나인 바닥의 미네랄과 연결되어 있기 때문에 중력의 영향을 받지 않는다. 그럼으로 위와 같은 조건이 발생시, 뒤에 짤 메서드인 미네랄 추락 메서드를 실행하면 안된다. 그럼으로 러프하게 리턴을 통해 해당 조건이 발생시 넘기도록 하였다.
나머지는 단순한 BFS를 사용하였다. 그럼으로 BFS관련 내용은 생략하겠다.
def bfs(x, y):
visitedBoard = [[False for _ in range(c)] for _ in range(r)]
visitedBoard[y][x] = True
needVisited = deque([[x, y]])
fallList = []
while needVisited:
nowX, nowY = needVisited.popleft()
if nowY == r - 1:
return
if board[nowY + 1][nowX] == '.':
fallList.append([nowX, nowY])
for i in range(4):
nextX, nextY = nowX + controlX[i], nowY + controlY[i]
if -1 < nextX < c and -1 < nextY < r:
if board[nextY][nextX] == 'x' and not visitedBoard[nextY][nextX]:
visitedBoard[nextY][nextX] = True
needVisited.append([nextX, nextY])
falling(visitedBoard, fallList)미네랄 추락 메서드
해당 메서드의 실행 조건은 미네랄 덩어리 확인 메서드에서 보듯이 바닥 미네랄과 연결되지 않았을 경우이다. 그럼으로 무조건 추락해야 한다는 가정으로 코드를 짜면 쉽게 생각할 수 있다.
우선 하나하나 따지기엔 경우가 많아질수 있기 때문에 현재 위치에서 얼마나 떨어질 수 있는지 추락 높이를 정한다면 쉽게 추락할 수 있을 것이다.
우선 떨어질 때 더이상 떨어질수 없는 조건은 아래와 같다.
- 바닥 도착시
- 떨어지는 위치 바로 아래에 다른 미네랄이 있는 경우
위의 조건을 통해 추락 높이를 알았다면 가장 바닥에 위치한 미네랄부터 추락 높이만큼 옮기면 된다. 아래는 해당 구현 코드이다.
def falling(visitedBoard, fallList):
fallDistance, flag = 1, False
floorHeight = r - 1
while True:
for x, y in fallList:
nextFallPosY = y + fallDistance
# 바닥 도착시, 더이상 떨어지지 않음
if nextFallPosY == floorHeight:
flag = True
break
# 떨어지려는 위치 바로 아래에 다른 미네랄이 있는 경우 더이상 떨어지지 않음
# 떨어지는 동안 클러스터 형태가 변하지 않는 조건있었기 때문에
if board[nextFallPosY + 1][x] == 'x' and not visitedBoard[nextFallPosY + 1][x]:
flag = True
break
if flag:
break
fallDistance += 1
for x in range(floorHeight - 1, -1, -1):
for y in range(c):
if board[x][y] == 'x' and visitedBoard[x][y]:
board[x][y] = '.'
board[x + fallDistance][y] = 'x'전체 코드
import sys
from collections import deque
def falling(visitedBoard, fallList):
fallDistance, flag = 1, False
floorHeight = r - 1
while True:
for x, y in fallList:
nextFallPosY = y + fallDistance
# 바닥 도착시, 더이상 떨어지지 않음
if nextFallPosY == floorHeight:
flag = True
break
# 떨어지려는 위치 바로 아래에 다른 미네랄이 있는 경우 더이상 떨어지지 않음
# 떨어지는 동안 클러스터 형태가 변하지 않는 조건있었기 때문에
if board[nextFallPosY + 1][x] == 'x' and not visitedBoard[nextFallPosY + 1][x]:
flag = True
break
if flag:
break
fallDistance += 1
for x in range(floorHeight - 1, -1, -1):
for y in range(c):
if board[x][y] == 'x' and visitedBoard[x][y]:
board[x][y] = '.'
board[x + fallDistance][y] = 'x'
def bfs(x, y):
visitedBoard = [[False for _ in range(c)] for _ in range(r)]
visitedBoard[y][x] = True
needVisited = deque([[x, y]])
fallList = []
while needVisited:
nowX, nowY = needVisited.popleft()
if nowY == r - 1:
return
if board[nowY + 1][nowX] == '.':
fallList.append([nowX, nowY])
for i in range(4):
nextX, nextY = nowX + controlX[i], nowY + controlY[i]
if -1 < nextX < c and -1 < nextY < r:
if board[nextY][nextX] == 'x' and not visitedBoard[nextY][nextX]:
visitedBoard[nextY][nextX] = True
needVisited.append([nextX, nextY])
falling(visitedBoard, fallList)
def throwStick(throwHeight, isLeftThrow):
crashPosX = 0
checkPosList = []
if isLeftThrow:
for i in range(c):
if board[throwHeight][i] == 'x':
board[throwHeight][i] = '.'
crashPosX = i
break
else:
for i in range(c - 1, -1, -1):
if board[throwHeight][i] == 'x':
board[throwHeight][i] = '.'
crashPosX = i
break
# 전체를 보는 것보다 한 묶음 단위로 보면 편하기 때문에
# 어떤 미네랄을 파괴했을 때, 중력으로 떨어지는 부분을 생각할 때 부서진 부분에 근접한 부분만 봐도 됨
# 예시) 어떤 미네랄을 파괴했을 때 중력에 영향을 받을 조건을 달성하기 위해서
# 그 부분이 미네랄과의 연결을 끊을 수 있는 부분이여야 함, 즉 파괴된 부분의 근접한 부분을
# 탐색해서 중력에 영향을 받을 수 있는지 조건을 따지면 전체를 탐색안해도 됨
for i in range(4):
nextX, nextY = crashPosX + controlX[i], throwHeight + controlY[i]
if -1 < nextX < c and -1 < nextY < r:
if board[nextY][nextX] == 'x':
checkPosList.append([nextX, nextY])
return checkPosList
def solution():
global r, c, board, controlX, controlY
input = sys.stdin.readline
r, c = map(int, input().split())
board = []
controlX = [1, -1, 0, 0]
controlY = [0, 0, 1, -1]
for _ in range(r):
board.append(list(input().rstrip('\n')))
n = int(input())
throwList = deque(map(int, input().split()))
isLeftThrow = True
while throwList:
throwHeight = r - throwList.popleft()
checkPosList = throwStick(throwHeight, isLeftThrow)
isLeftThrow = not isLeftThrow
for i in checkPosList:
checkPosX, checkPosY = i[0], i[1]
bfs(checkPosX, checkPosY)
for i in board:
print(' '.join(i))
solution()