[BOJ] 2933. 미네랄(Python) / Simulation + BFS

2933번: 미네랄

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하는 문제

# 2시간 48분 소요

• 사용 알고리즘 : Simulation + BFS
• 구현이 상당히 까다로운 문제였다. 엣지 케이스가 많다.. 질문 게시판에 나온 모든 반례를 넣으며 코드를 고쳤고, 결국 pass!
• pass 후 거의 1-2시간을 더 투자해 최적화했고 시간 1위를 달성했다!(248ms, PyPy3 제출)
• 고려할 것이 많으므로 기능화한 함수를 만들어 구현했다.
• 크게 아래 5단계 흐름으로 코드를 짰다. 주석으로 설명이 더 잘 되어있긴 하다 ㅋㅋ 
  1. Input 받은 정보를 바탕으로 미네랄을 깨는 높이를 배열에서 사용하는 인덱스로 바꿔 미네랄 깨는 함수 호출.
     1. 이 때, 깬 부분을 인자(br, bc)로 넘긴다.
  2. 미네랄 깨는 함수에서 우선 땅에 붙어 있는 미네랄을 check배열에 1로 표시한다.
  3. 깨진 부분의 상하좌우 4방향을 확인해 땅에 붙어 있지 않은 미네랄이면 그 부분을 시작으로 BFS로 공중에 떠 있는 미네랄을 2로 표시하며 위치 좌표를 minerals 리스트에 담는다.(미네랄 떨어질 때 사용)
     1. 이 때, 좌표를 큐에서 꺼내면서 해당 좌표의 바로 아래 칸이 빈 칸이면 fallLst에 담아준다.(떨어질 칸 수 구하는데 사용)
  4. fallLst에 담긴 떨어질 미네랄 좌표가 있다면, checkDownCnt 함수에서 몇 칸 떨어질 지 최대 칸 수가 리턴됨
     1. 개인적으로 이 함수를 생각해내는 게 가장 오래 걸렸다..
  5. 떨어질 칸의 수(downCnt)가 정해지면, 공중에 떠있는 미네랄의 위치를 담은 리스트(minerals)에서 좌표를 하나씩 꺼내며 떨어질 칸의 수만큼 내려 cave 배열에 반영한다.

 

내게 가장 도움이 된 테스트케이스 반례이다.

Input:

4 4

xxxx

xx.x

x..x

...x 

1

3

 

Answer:

xxxx

.x.x

...x

x..x

 

파이썬 코드는 다음과 같다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

# 미네랄 떨어질 수 있는지 칸 세기
def checkDownCnt(fallLst, check):
    downCnt, flag = 1, 0      # downCnt 크기 1씩 늘려가며
    while True:
        for r, c in fallLst:
            if r+downCnt == R-1:        # 땅을 만나거나
                flag = 1
                break
            if cave[r+downCnt+1][c] == 'x' and check[r+downCnt+1][c]:   # 다른 미네랄 만나면
                flag = 1
                break
        if flag:    # 그 때가 떨어질 수 있는 최대 downCnt 값
            break
        downCnt += 1
    return downCnt

def checkLand():
    check = [[0] * C for _ in range(R)]
    # 땅에 붙어 있는 미네랄 check 배열에 표시
    for lc in range(C):
        if cave[R-1][lc] == "x" and not check[R-1][lc]:     # 미네랄이면서 첫 방문이면
            check[R-1][lc] = 1
            Q = deque([(R-1, lc)])
            while Q:
                r, c = Q.popleft()
                for d in range(4):
                    nr = r + dr[d]
                    nc = c + dc[d]
                    if not (0 <= nr < R and 0 <= nc < C):       # 격자 밖이면
                        continue
                    if cave[nr][nc] == "x" and not check[nr][nc]:   # 미네랄이거나 방문한 적 없으면
                        check[nr][nc] = 1
                        Q.append((nr, nc))
    return check


def breakMinerals(br, bc):
	# 2단계 - 땅에 붙어 있는 미네랄 1로 표시되어 있는 맵 리턴
    check = checkLand()

	# 3단계 - 공중에 떠있는 미네랄 2로 표시, 동굴에서 지우기
    minerals = []    # 공중에 떠있는 미네랄 리스트
    fallLst = []     # 떨어질 수 있는 클러스터의 아랫부분만 저장
    for nd in range(4):     # 깨진 곳 기준으로 4방향 확인
        r = br + dr[nd]
        c = bc + dc[nd]
        if not (0 <= r < R and 0 <= c < C):
            continue

        # 미네랄인데 땅에 붙어 있지 않다면(check 배열에서 0으로 표시되어 있다면) 2로 표시
        if cave[r][c] == "x" and not check[r][c]:
            Q = deque([(r, c)])
            check[r][c] = 2
            minerals.append((r, c))
            cave[r][c] = "."
            while Q:
                r, c = Q.popleft()
                if cave[r+1][c] == ".":     # 바로 밑이 빈 공간인 미네랄
                    fallLst.append((r, c))
                for d in range(4):
                    nr = r + dr[d]
                    nc = c + dc[d]
                    if not (0 <= nr < R and 0 <= nc < C):
                        continue
                    if cave[nr][nc] == "x" and not check[nr][nc]:
                        check[nr][nc] = 2           # 공중에 떠있는 미네랄 클러스터 표시
                        Q.append((nr, nc))
                        minerals.append((nr, nc))   # 미네랄 위치 리스트에 담기
                        cave[nr][nc] = "."          # 동굴에서 공중에 떠 있는 미네랄 제거

    if fallLst:    # 공중에 떠있는 미네랄이 있다면
    	# 4단계 - 떨어질 최대 칸의 수 리턴
        downCnt = checkDownCnt(fallLst, check)

        # 5단계 - 미네랄 떨어질 위치 동굴에 그리기
        for mr, mc in minerals:
            cave[mr+downCnt][mc] = "x"

# main
R, C = map(int, input().split())
cave = [list(input().rstrip()) for _ in range(R)]
N = int(input())
heights = list(map(int, input().split()))

# 1단계 - 좌우에서 막대기 던져 미네랄 깨기
for i in range(N):
    br = R - heights[i]
    if not i % 2:       # 왼쪽에서 깸
        for bc in range(C):
            if cave[br][bc] == "x":
                cave[br][bc] = "."
                breakMinerals(br, bc)   # 깨진 위치 인자로 넘겨 미네랄 깨기
                break
    else:               # 오른쪽에서 깸
        for bc in range(C-1, -1, -1):
            if cave[br][bc] == "x":
                cave[br][bc] = "."
                breakMinerals(br, bc)
                break
    
# 형식에 맞게 출력
for row in cave:
    print(''.join(row))

---

• 시간 : 248ms / 메모리 : 128000kb(PyPy3 제출, 시간 1위 달성!)
• 고찰 : 구현이 까다로운 골드 3 문제였다. 사실 구현이 까다롭다기보다 공중에 떠있는 미네랄의 떨어질 칸 수 구하는 데 엣지 케이스가 많아 고려하며 코드를 짜는게 힘들었다. 그만큼 기능화/최적화하느라 노력했고, 시간 1위를 달성해서 기분 좋아따!!!! 시간을 많이 투자한 만큼 배운 점이 많은 문제였다. 비슷한 문제가 나오면 잘 풀어낼 수 있을 것 같다^_^