[파이썬] 백준 2993 : 미네랄 (골드1)

[파이썬] 백준 2993 : 미네랄 (골드1)

2933번: 미네랄

---

문제

---

풀이

 

0. 방향성 생각

• enumerate로 순서 받아서 좌 우 파괴하기
• BFS로 군집 탐색해서 아래부분 얼마나 떨어지는지 확인하기
• 떨어지는 좌표 집합으로 구현하기.

1. 입력

from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
t = int(input())
test = list(map(int,input().split()))

• 입력 받아주기

 

2. 미네랄 파괴 함수 정의

def destroy(index,height):
    if index%2:
        for x in range(w-1,-1,-1):
            if arr[-height][x] == 'x':
                arr[-height][x] = '.'
                return (x,h-height)
    else:
        for x in range(w):
            if arr[-height][x] == 'x':
                arr[-height][x] = '.'
                return (x,h-height)
    return None

• 허공에 삽질하는 경우는 None 리턴
• 그렇지 않은 경우는 index(순서)에서 짝 홀 구분해서 짝수면 왼쪽부터, 홀수면 오른쪽부터 탐색해서 미네랄 파괴하고 파괴한 위치 리턴

3. BFS 함수 구현

 

dire = [(1,0),(0,1),(-1,0),(0,-1)]
def bfs(x,y):

    q = deque([(x,y)])
    visit[y][x] = True
    info = {x:[y]}
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx = x + dx
            ny = y + dy
            if 0<=nx<w and 0<=ny<h and not visit[ny][nx]:
                if arr[ny][nx] == 'x':
                    visit[ny][nx] = True
                    q.append((nx,ny))
                    if nx in info: info[nx].append(ny)
                    else: info[nx] = [ny]
    levitate = True
    temp = []
    for x in info.keys():
        info[x].sort()
        temp.append(info[x][-1])

    if max(temp) == h-1: levitate = False
    return info,levitate

• BFS로 군집 탐색
• info[x좌표] = [y1,y2...,yk] 꼴로 저장
• 찾은 군집 중 가장 큰 y좌표들을 temp에 저장
• temp에서 가장 큰 원소가 h-1일 경우 땅에 붙어있다.
• 군집 정보 info와 공중부양 정보 levitate를 리턴한다

4. 떨어지는 거리 계산하는 함수 정의

def cal_dist(info):
    min_ds = [(x,info[x][-1]) for x in info.keys()]
    min_d = 101
    for x,y in min_ds:
        for i in range(y+1,h):
            if arr[i][x] == 'x':
                min_d = min(min_d,i-y)
                break
            min_d = min(min_d,h-y)
    return min_d-1

• 앞에서 구한 info정보를 이용해서 가장 바닥에 있는 좌표들 찾기. (BFS에서 구한거라서 리턴하면 더 빨라질듯)
• 바닥 혹은 아래쪽 미네랄과 거리차이가 얼마나 나는지 확인

5. 떨어지는 함수 정의

def falling(move_dist,info):
    
    before = set()
    for x in info.keys():
        for y in info[x]:
            before.add((x,y))
    
    after = set()
    for x,y in before:
        after.add((x,y+move_dist))
        
    for x,y in after|before:
        if 0<=x<w and 0<=y<h:
            if (x,y) in after: arr[y][x] = 'x'
            else: arr[y][x] = '.'

• 군집 좌표를 before에 모두 넣는다.
• 떨어진 후 군집 좌표를 after에 넣는다.
• 합집합이 after에 속하면 미네랄이 떨어진 위치이고, 아닌 경우 미네랄이 사라진 위치이다.

 

6. 시뮬레이션

for idx,hei in enumerate(test):
    
    loc = destroy(idx,hei)
    
    if loc == None:
        continue
    else:
        x,y = loc
        if idx%2: check = [(x-1,y),(x,y-1),(x,y+1)]
        else: check = [(x+1,y),(x,y-1),(x,y+1)]
        
        visit = [[False]*w for _ in range(h)]
        for j,i in check:
            if 0<=j<w and 0<=i<h and arr[i][j] == 'x' and not visit[i][j]:
                infos,levi = bfs(j,i)
                if levi:
                    move_d = cal_dist(infos)
                    falling(move_d,infos)

for row in arr:
    print(''.join(row))

• 파괴한 위치에서 앞 위 아래를 확인해야한다. 아래쪽 확인 안해서 틀렸었음...

---

전체코드

from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
t = int(input())
test = list(map(int,input().split()))


def destroy(index,height):
    if index%2:
        for x in range(w-1,-1,-1):
            if arr[-height][x] == 'x':
                arr[-height][x] = '.'
                return (x,h-height)
    else:
        for x in range(w):
            if arr[-height][x] == 'x':
                arr[-height][x] = '.'
                return (x,h-height)
    return None

dire = [(1,0),(0,1),(-1,0),(0,-1)]
def bfs(x,y):

    q = deque([(x,y)])
    visit[y][x] = True
    info = {x:[y]}
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx = x + dx
            ny = y + dy
            if 0<=nx<w and 0<=ny<h and not visit[ny][nx]:
                if arr[ny][nx] == 'x':
                    visit[ny][nx] = True
                    q.append((nx,ny))
                    if nx in info: info[nx].append(ny)
                    else: info[nx] = [ny]
    levitate = True
    temp = []
    for x in info.keys():
        info[x].sort()
        temp.append(info[x][-1])

    if max(temp) == h-1: levitate = False
    return info,levitate

def cal_dist(info):
    min_ds = [(x,info[x][-1]) for x in info.keys()]
    min_d = 101
    for x,y in min_ds:
        for i in range(y+1,h):
            if arr[i][x] == 'x':
                min_d = min(min_d,i-y)
                break
            min_d = min(min_d,h-y)
    return min_d-1

def falling(move_dist,info):
    
    before = set()
    for x in info.keys():
        for y in info[x]:
            before.add((x,y))
    
    after = set()
    for x,y in before:
        after.add((x,y+move_dist))
        
    for x,y in after|before:
        if 0<=x<w and 0<=y<h:
            if (x,y) in after: arr[y][x] = 'x'
            else: arr[y][x] = '.'


for idx,hei in enumerate(test):
    
    loc = destroy(idx,hei)
    
    if loc == None:
        continue
    else:
        x,y = loc
        if idx%2: check = [(x-1,y),(x,y-1),(x,y+1)]
        else: check = [(x+1,y),(x,y-1),(x,y+1)]
        
        visit = [[False]*w for _ in range(h)]
        for j,i in check:
            if 0<=j<w and 0<=i<h and arr[i][j] == 'x' and not visit[i][j]:
                infos,levi = bfs(j,i)
                if levi:
                    move_d = cal_dist(infos)
                    falling(move_d,infos)

for row in arr:
    print(''.join(row))

 

코멘트

문제가 미네랄 2보다 러프하게 풀어도 맞을 수 있다고 하네요..