[BOJ/백준] 2933 미네랄

# 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가지 부분이 이 문제를 푸는데 어려움을 겪었던 부분이었다.