[파이썬/python] 백준 - 18500 미네랄 2

문제

https://www.acmicpc.net/problem/18500

---

문제 설명

1.   평면 형태의 동굴이 입력으로 주어진다.
   1. 동굴에는 미네랄이 존재한다.('x')
   2. 미네랄이 붙어있으면 하나의 클러스터로 판단한다.
2. 두 명의 사람이 막대기를 왼쪽,오른쪽에서 번갈아가며 던진다.
   1. 던졌을 때 미네랄이 있다면 부셔진다.
   2. 동시에 두 개 이상의 클러스터가 떨어지는 경우는 없다.
3. 입력으로 주어진 높이 순서대로 막대기를 던진 후 동굴의 결과 상태를 출력한다.     

 

---

풀이

문제 이해하기 굉장히 어려운 문제였다.

예제 2번을 예시로 설명해보겠다.

 

초기 상태 

초기 아래와 같은 동굴이 입력되고, [6,6,4,3,1] 높이 순서대로 막대기를 던진다. 

높이는 아래서부터 1~8 순이다.

........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.

 

 

1번 막대기 (왼쪽)

높이 = 6으로 막대기를 던진다.

6 높이에서 왼쪽부터 차례대로 보며 미네랄이 나오면 파괴한다.

현재까지 모든 미네랄이 땅에 붙어있는 상태로 있으므로 아래로 미네랄을 이동시키지 않는다. 

........
........
.....xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.

 

 

2번 막대기 (오른쪽)

높이 = 6으로 막대기를 던진다.

6 높이에서 오른쪽부터 차례대로 보며 미네랄이 나오면 파괴한다.

현재까지 모든 미네랄이 땅에 붙어있는 상태로 있으므로 아래로 미네랄을 이동시키지 않는다.

........
........
.....x..
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.

 

3번 막대기 (왼쪽)

높이 = 4로 막대기를 던진다.

4 높이에서 왼쪽부터 차례대로 보며 미네랄이 나오면 파괴한다.

현재까지 모든 미네랄이 땅에 붙어있는 상태로 있으므로 아래로 미네랄을 이동시키지 않는다.

........
........
.....x..
...xxx..
...xx...
..x.xxx.
..x...x.
.xxx..x.

 

4번 막대기 (오른쪽)

높이 = 3로 막대기를 던진다.

3 높이에서 오른쪽부터 차례대로 보며 미네랄이 나오면 파괴한다.

미네랄 8개가 공중에 떠 있으므로 아래로 떨어트린다. 

........
........
.....x..
...xxx..
...xx...
..x.xx..
..x...x.
.xxx..x.

4번 막대기 (오른쪽) - 클러스터 아래로 이동

클러스터 조각을 아래로 이동시킨다.

........
........
........
........
.....x..
..xxxx..
..xxxxx.
.xxxxxx.

 

5번 막대기 (왼쪽)

높이 = 1로 막대기를 던진다.

1 높이에서 왼쪽부터 차례대로 보며 미네랄이 나오면 파괴한다.

현재까지 모든 미네랄이 땅에 붙어있는 상태로 있으므로 아래로 미네랄을 이동시키지 않는다.

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

---

코드

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

R,C = map(int,input().split())

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

board = [list(input().strip()) for _ in range(R)]



def bfs(sy,sx):
    queue = deque([(sy,sx)])
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny > R-1 or nx < 0 or nx > C-1 or board[ny][nx] =='.':
                continue
            if ny == R-1:
                up.clear()
                return 0
            if not visited[ny][nx]:
                up.append((ny,nx))
                queue.append((ny,nx))
                visited[ny][nx] = 1
    return 1

def move():
    min_height = R+1
    up.sort(key = lambda x: -x[0])
    for y,x in up:
        cnt = 0
        for ny in range(y+1,R):
            if visited[ny][x] == 1:
                cnt = R+1
                break
            if board[ny][x] == '.':
                cnt += 1
            else:
                break
        min_height = min(min_height,cnt)
    
    for y,x in up:
        board[y][x] = '.'
        board[y+min_height][x] = 'x'

def print_result():
    for i in board:
        print(''.join(i))

# d가 짝수면 왼쪽, 홀수면 오른쪽
int(input())
d = 0
heights = list(map(int,input().split()))
for h in heights:
    exist = 0
    up = []
    h = R-h
    if d % 2 == 0:
        for x in range(C):
            if board[h][x] == 'x':
                board[h][x] = '.'
                visited = [[0 for _ in range(C)] for _ in range(R)]
                break
    else:
        for x in range(C-1,-1,-1):
            if board[h][x] == 'x':
                board[h][x] = '.'
                visited = [[0 for _ in range(C)] for _ in range(R)]
                break           
    for j in range(4):
        nh = h + dy[j]
        nx = x + dx[j]
        if nh < 0 or nh > R-1 or nx < 0 or nx > C-1:
            continue
        if board[nh][nx] == 'x': 
            up.append((nh,nx))
            visited[nh][nx] = 1
            exist = bfs(nh,nx)
        if exist:
            break
        visited = [[0 for _ in range(C)] for _ in range(R)]

    #아래로 내리기
    if up:
        move()
    d+=1
print_result()

---

시간복잡도

• 막대기를 던지는 횟수(N) * (열 탐색 횟수(C) +  4방향 BFS*(4*R*C) + 클러스터 아래로 이동)
• 최악일 경우 N = 100, C = 100, BFS = 4*100*100 이다.
• 따라서 약 O(10^6)의 시간복잡도가 소요된다.