# R,C 행,열
# 같은 클러스터
# 창영 동굴 왼쪽, 상근 오른쪽
from collections import deque
def BreakMineral(height,flag):
y_list = sorted(list(range(C)),reverse=flag)
height = R - height
for y in y_list:
if cave[height][y] == 'x':
cave[height][y] = '.'
return [height,y]
return [-1,-1]
def DownCluster(input_point,flag):
dx = [0,-1,0,1]
dy = [1,0,-1,0]
x,y = input_point
cluster_entry = []
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<R and 0<=ny<C:
if cave[nx][ny] == 'x':
cluster_entry.append((nx,ny))
cluster_list = []
copy_cave = [row[:] for row in cave]
for point in cluster_entry:
if cave[point[0]][point[1]] == 'x':
visited = set()
stack = deque()
stack.append(point)
visited.add(point)
while stack:
x,y = stack.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<R and 0<=ny<C:
if cave[nx][ny] == 'x' and ((nx,ny)) not in visited:
visited.add((nx,ny))
stack.append((nx,ny))
visited = list(visited)
flag = True
for point in visited:
if point[0] == (R-1):
flag = False
break
if flag:
for point in visited:
cave[point[0]][point[1]] = '.'
cluster_list.append(visited)
if cluster_list:
for cluster in cluster_list:
origin_cluster = [row[:] for row in cluster]
while True:
move_point = []
flag = False
for point in cluster:
nx = point[0]+1
ny = point[1]
if 0<=nx<R and cave[nx][ny] == '.':
move_point.append((nx,ny))
else:
flag = True
break
else:
cluster = [row[:] for row in move_point]
if flag:
break
for point in origin_cluster:
copy_cave[point[0]][point[1]] = '.'
for point in cluster:
copy_cave[point[0]][point[1]] = 'x'
return copy_cave
R,C = map(int,input().split())
cave = [list(input()) for _ in range(R)]
N = int(input())
arr = list(map(int,input().split()))
for i in range(N):
if i%2:
break_point = BreakMineral(arr[i],True)
if break_point != [-1,-1]:
cave = DownCluster(break_point,True)
else:
break_point = BreakMineral(arr[i],False)
if break_point != [-1,-1]:
cave = DownCluster(break_point,False)
for row in cave:
print(''.join(row))
시뮬레이션을 해서 푸는 문제였다. 이 문제에서 좌우를 번갈아 가면서 진행이 되기때문에 flag라는 속성을 줘서 구분을 해줬다.
BreakMineral이라는 함수는 막대를 던져 부서진 위치를 찾기 위함이다. 만약 하나도 부셔지지 않았다면 -1,-1을 반환하게 만들어줬다.
여기서 중요한 부분은 DownCluster 함수이다. 부서진 점을 위치로 해서, 상하좌우에 존재하는 미네랄이 있는지 확인을 한다.
그리고 그 미네랄을 너비우선탐색으로 확인하여, 만약에 (R-1) 즉 지면과 맞닿아 있으면, 낙하를 하지 않는 클러스터임을 알 수 있다.
그리고 지표면과 맞닿지 않는 클러스터들은 낙하하게 될 클러스터 이므로, 있던 위치들을 빈공간 '.'으로 만들어준다.
이렇게 모은 클러스터들을 한칸씩 움직이면서, 지표면과 맞닿는지? 아니면 다른 클러스터와 닿는지 x축 값만 증가시키면서 확인해준다.
멈추는 위치를 발견하면 그 위치에 'x'로 표시를 해주었다.
# R,C 행,열
# 같은 클러스터
# 창영 동굴 왼쪽, 상근 오른쪽
from collections import deque
def BreakMineral(height,flag):
y_list = sorted(list(range(C)),reverse=flag)
height = R - height
for y in y_list:
if cave[height][y] == 'x':
cave[height][y] = '.'
return [height,y]
return [-1,-1]
def DownCluster(input_point,flag):
dx = [0,-1,0,1]
dy = [1,0,-1,0]
x,y = input_point
cluster_entry = []
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<R and 0<=ny<C:
if cave[nx][ny] == 'x':
cluster_entry.append((nx,ny))
cluster_list = []
for point in cluster_entry:
if cave[point[0]][point[1]] == 'x':
stack = [point]
visited = set()
visited.add(point)
flag = True
while stack:
x,y = stack.pop(0)
if x == (R-1):
flag = False
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<R and 0<=ny<C:
if cave[nx][ny] == 'x' and ((nx,ny)) not in visited:
visited.add((nx,ny))
stack.append((nx,ny))
if flag:
visited = list(visited)
for point in visited:
cave[point[0]][point[1]] = '.'
cluster_list.append(visited)
for cluster in cluster_list:
move = 1
flag = True
while flag:
for x,y in cluster:
if x+move+1<R and cave[x+move+1][y] == '.':
continue
else:
flag = False
break
else:
move += 1
for x,y in cluster:
cave[x+move][y] = 'x'
R,C = map(int,input().split())
cave = [list(input()) for _ in range(R)]
N = int(input())
arr = list(map(int,input().split()))
for i in range(N):
if i%2:
break_point = BreakMineral(arr[i],True)
if break_point != [-1,-1]:
DownCluster(break_point,True)
else:
break_point = BreakMineral(arr[i],False)
if break_point != [-1,-1]:
DownCluster(break_point,False)
for row in cave:
print(''.join(row))이 부분은 좀 더 나은 풀이이다.
이 문제를 풀면서 크게 2가지 부분에서 실수를 했었다.
먼저 낙하하는 클러스터가 생길수 있는 위치를 던지는 방향의 y축방향과 -x 방향만 생길수 있다고 생각했다.
하지만 그럴경우
4 4
xxxx
xx.x
x..x
...x
1
3
와 같은 경우엔 밑에 있는 미네랄이 떨어짐을 알 수 있다. 그래서 그부분을 고쳐주었다.
두번째로 어려웠던 부분은 클러스터들을 낙하시키는것이었다. 클러스터의 복제위치 및 클러스터들이 낙하할때 탐색할 배열을 선정하는데 어려움을 겪었다.
처음 풀었을때는 원본배열을 복사하고, 옮기는 방식으로 했지만,
두번째로 푼 코드는 원본배열에서 그대로 작업을 해주었다.
이 2가지 부분이 이 문제를 푸는데 어려움을 겪었던 부분이었다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 20366 같이 눈사람 만들래? (0) | 2021.05.14 |
|---|---|
| [BOJ/백준] 1194 달이 차오른다 가자 (0) | 2021.05.11 |
| [BOJ/백준] 1126 같은 탑 (0) | 2021.05.02 |
| [BOJ/백준] 1071 소트 (0) | 2021.05.02 |
| [BOJ/백준] 1062 가르침 (0) | 2021.05.02 |