문제 링크
문제 설명
높이 R 길이 C의 동굴이 있다. 동굴엔 미네랄이 저장되어 있고, 인접한 두 미네랄은 같은 클러스터에 속한다고 한다. 동굴의 왼쪽, 오른쪽 양 끝에 선 창영이와 상근이가 특정 높이로 막대기를 번갈아가면서 던진다. 막대는 땅과 수평을 이루면서 날아가는데, 미네랄을 만나면 해당 칸의 미네랄을 박살내고 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 공중에 떠 있는 경우에는 중력에 의해서 다른 클러스터 위나 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다.
동굴 안의 미네랄 모양과 두사람이 막대기를 던질 높이가 주어졌을때, 막대기를 모두 던진 후 동굴 안의 미네랄 모양을 출력하라.
IN
동굴의 높이 R, 길이 C
다음 R개의 줄에 동굴 속 미네랄의 모양이 주어짐 (.은 빈칸, x는 미네랄)
막대를 던진 횟수 N
막대를 던진 높이들 -> 1은 동굴의 바닥, R은 동굴의 제일 위
문제 풀이
각각의 막대기 던지기에 대해서
- 미네랄 부시기
해당 높이에서 처음 만나는 미네랄 부시기 (.->x)
def attack_mineral(i):
if i % 2 == 0:
#왼쪽에서부터 공격
j = 0
while j < C :
if cave[attacks[i]][j] == 'x':
break
j += 1
else:
#오른쪽에서부터 공격
j = C-1
while j >= 0:
if cave[attacks[i]][j] == 'x':
break
j -= 1
return j
j = attack_mineral(i)
if j in range(C):
if cave[attacks[i]][j] == 'x':
cave[attacks[i]][j] = '.'- 부서지고 남은 클러스터가 공중에 떠있는지 검사
2.1 부신 미네랄(i,j)의 동서남북 4방향에 미네랄이 있는지 검사
2.2 있으면 bfs를 이용해서 해당 클러스터를 찾기
-> 클러스터가 바닥에 닿아있으면 아래로 떨어뜨릴 필요가 없으므로 바닥에 닿았는지 검사한다.
def get_mineral(x, y):
queue = deque([(x, y)])
visited = [[-1]*C for _ in range(R)]
visited[x][y] = 1
cluster = [[x, y]]
while queue:
x, y = queue.popleft()
#클러스터 찾기
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx == R:
#바닥에 닿아있으면 -> 아래로 떨어뜨릴 필요 x
return []
if in_range(nx, ny) and cave[nx][ny] == 'x' and visited[nx][ny] == -1:
visited[nx][ny] = 1
queue.append((nx, ny))
cluster.append([nx, ny])
return cluster- 공중에 떠있는 클러스터가 있으면 다른 클러스터나 바닥에 닿을때까지 내려준다.
클러스터에서 가장 밑에 있는 미네랄부터 차례대로 한칸씩 내려주기 위해서 내림차순으로 정렬을 한다.
클러스터를 구성하는 모든 미네랄을 한칸씩 내려줘야 하는데, 각각의 미네랄을 검사할때 한 미네랄이 바닥이나 다른 클러스터에 닿으면 이번turn 의 이동을 전부 취소하고 이전 이동을 move의 최종 결과로 return해야 한다. 이전 이동의 취소를 구현하기 위해서 cave와 cluster는 deepcopy를 이용해서 복사해놓고, 모든 미네랄이 칸 이동에 성공했을때 cave와 cluster를 갱신해줬다.
def move_mineral(cluster, cave):
cluster = sorted(cluster, key = lambda x : (-x[0], -x[1]))
#한칸씩 내리기
while True:
ccluster = copy.deepcopy(cluster)
ccave = copy.deepcopy(cave)
for c in ccluster:
if c[0]+1 == R or ccave[c[0]+1][c[1]] == 'x':
#다른 미네랄과 닿거나 바닥에 닿으면,
return cluster, cave
else:
ccave[c[0]][c[1]] = '.'
ccave[c[0]+1][c[1]] = 'x'
c[0] += 1
else:
cluster = ccluster
cave = ccave전체 코드
전체 코드는 다음과 같다.
import sys
from collections import deque
import copy
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
R, C = map(int, input().split())
cave = []
for _ in range(R):
cave.append(list(input().strip()))
N = int(input())
attacks = list(map(int, input().split()))
for i in range(len(attacks)):
attacks[i] = R - attacks[i]
def print_cave(cave):
for i in range(len(cave)):
for j in range(len(cave[0])):
print(cave[i][j], end='')
print()
def in_range(x, y):
if x in range(R) and y in range(C):
return True
else:
return False
def attack_mineral(i):
if i % 2 == 0:
#왼쪽에서부터 공격
j = 0
while j < C :
if cave[attacks[i]][j] == 'x':
break
j += 1
else:
#오른쪽에서부터 공격
j = C-1
while j >= 0:
if cave[attacks[i]][j] == 'x':
break
j -= 1
return j
def get_mineral(x, y):
queue = deque([(x, y)])
visited = [[-1]*C for _ in range(R)]
visited[x][y] = 1
cluster = [[x, y]]
while queue:
x, y = queue.popleft()
#클러스터 찾기
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx == R:
#벽에 닿아있으면 -> 아래로 떨어뜨릴 필요 x
return []
if in_range(nx, ny) and cave[nx][ny] == 'x' and visited[nx][ny] == -1:
visited[nx][ny] = 1
queue.append((nx, ny))
cluster.append([nx, ny])
return cluster
def move_mineral(cluster, cave):
cluster = sorted(cluster, key = lambda x : (-x[0], -x[1]))
#한칸씩 내리기
while True:
ccluster = copy.deepcopy(cluster)
ccave = copy.deepcopy(cave)
for c in ccluster:
if c[0]+1 == R or ccave[c[0]+1][c[1]] == 'x':
#다른 미네랄과 닿거나 바닥에 닿으면,
return cluster, cave
else:
ccave[c[0]][c[1]] = '.'
ccave[c[0]+1][c[1]] = 'x'
c[0] += 1
else:
cluster = ccluster
cave = ccave
for i in range(N):
#미네랄 부시기
j = attack_mineral(i)
if j in range(C):
if cave[attacks[i]][j] == 'x':
cave[attacks[i]][j] = '.'
#공중에 떠있는 미네랄 검사
for k in range(4):
nx, ny = attacks[i]+dx[k], j+dy[k]
if in_range(nx, ny) and cave[nx][ny] == 'x':
cluster = get_mineral(nx, ny)
if cluster:
cluster, cave = move_mineral(cluster, cave)
break
print_cave(cave)느낀점
공중에 떠있는 클러스터를 move()로 한칸씩 이동시킬때, 내림차순 정렬을 하지 않아서 한참 헤맸다 ,,^^ 낫이지 ,,
Hongik CE