[BOJ / 백준] 2933번 미네랄 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/2933

2933번: 미네랄

 

 

 

 

풀이

💡 idea

1. 왼쪽 → 오른쪽 / 오른쪽 → 왼쪽 순서에 맞게 미네랄을 파괴한다

2. 파괴한 미네랄의 인접한 미네랄 덩어리(클러스터)를 찾아 떠있는 상태인지 확인한다

    - 파괴한 미네랄과 인접 미네랄 : 파괴 이전에 같은 클러스터

3. 해당 클러스터가 떠있는 상태라면 떨어뜨리기!

    - 위 그림에서 보라색 미네랄이 파괴되었을 때, 오른쪽과 같이 인접해있는 파란색 미네랄 덩어리(클러스터)가 바닥에 떨어진다

 

💡 implementation

def find_cluster(cave, a, b):
    isFloating = True
    visited = [[False] * len(cave[0]) for _ in range(len(cave))]
    cluster = []
    
    q = deque([(a, b)])
    visited[a][b] = True

    while q:
        x, y = q.popleft()
        cluster.append((x, y))
        if x == 0:
            isFloating = False

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < len(cave) and 0 <= ny < len(cave[0]) and not visited[nx][ny] and cave[nx][ny] == 'x':
                q.append((nx, ny))
                visited[nx][ny] = True
    
    return isFloating, cluster

- BFS로 파괴된 미네랄 인접 클러스터 찾기

- 클러스터에 속한 미네랄을 탐색하던 중 바닥에 있는 (x == 0) 미네랄을 찾은 경우, 해당 클러스터가 떠있지 않다고 볼 수 있다

 

def drop_cluster(cave, clusters):
    ncave = [t[:] for t in cave]
    drop = 1
    clusters.sort()
    while True:
        for x, y in clusters:
            if x - drop == -1 or (cave[x - drop][y] == 'x' and not (x - drop, y) in clusters):
                for cx, cy in clusters:
                    ncave[cx - drop + 1][cy] = 'x'
                    ncave[cx][cy] = '.'
                return ncave

        drop += 1

- 한칸씩 떨어진다 가정하여 떨어질 수 있는지 확인 후, 떨어질 수 없거나 바닥인 경우에 클러스터 옮기기

 

 

 

 

 

 

CODE

import sys
from collections import deque
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def find_cluster(cave, a, b):
    isFloating = True
    visited = [[False] * len(cave[0]) for _ in range(len(cave))]
    cluster = []
    
    q = deque([(a, b)])
    visited[a][b] = True

    while q:
        x, y = q.popleft()
        cluster.append((x, y))
        if x == 0:
            isFloating = False

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < len(cave) and 0 <= ny < len(cave[0]) and not visited[nx][ny] and cave[nx][ny] == 'x':
                q.append((nx, ny))
                visited[nx][ny] = True
    
    return isFloating, cluster

def drop_cluster(cave, clusters):
    ncave = [t[:] for t in cave]
    drop = 1
    clusters.sort()
    while True:
        for x, y in clusters:
            if x - drop == -1 or (cave[x - drop][y] == 'x' and not (x - drop, y) in clusters):
                for cx, cy in clusters:
                    ncave[cx - drop + 1][cy] = 'x'
                    ncave[cx][cy] = '.'
                return ncave

        drop += 1


r, c = map(int, input().split())
cave = [[] for _ in range(r)]

for i in range(r):
    cave[r - i - 1] = list(input().strip())

n = int(input())
heights = list(map(int, input().split()))

for i, h in enumerate(heights):
    # 파괴될 미네랄 찾기
    isBroken = False
    if i % 2 == 0:  # 창영 (왼쪽 -> 오른쪽)
        j = 0
        while j < c:
            if cave[h - 1][j] == 'x':
                bx, by = h - 1, j
                isBroken = True
                break
            j += 1
    else:           # 상근 (오른쪽 -> 왼쪽)
        j = c - 1
        while j >= 0:
            if cave[h - 1][j] == 'x':
                bx, by = h - 1, j
                isBroken = True
                break
            j -= 1

    if isBroken:
        cave[bx][by] = '.'  # 미네랄 파괴

        # 파괴된 미네랄이 인접 클러스터 찾기
        for dir in range(4):
            nx = bx + dx[dir]
            ny = by + dy[dir]
            if 0 <= nx < r and 0 <= ny < c and cave[nx][ny] == 'x':
                # 클러스터 + 떠있는 클러스터인지 찾기
                isFloating, cluster = find_cluster(cave, nx, ny)

                if isFloating:  # 떠있는 클러스터라면 떨어뜨리기
                    cave = drop_cluster(cave, cluster)

for c in cave[::-1]:
    for cc in c:
        print(cc, end='')
    print()

 

 

 

 

 

결과