[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 25331번 _ Drop 7

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

25331번: Drop 7

[문제]

Drop7은 7×7 크기의 격자에서 진행하는 싱글 플레이어 게임이다. 처음에는 격자가 비어있고, 플레이어는 매 턴마다 1 이상 7 이하의 정수 하나가 적힌 공을 받아 7개의 열 중 한 곳에 떨어뜨려야 한다. 떨어뜨린 공은 이미 배치되어 있는 공 바로 위에 도달하거나 바닥 바로 위에 도달할 때까지 아래로 이동한다.

가로 방향으로 연속해서 놓여있는 공들을 "가로 방향 그룹", 세로 방향으로 연속해서 놓여있는 공들을 "세로 방향 그룹"이라고 하자. 공을 떨어뜨릴 때마다 공들의 그룹이 바뀔 수 있는데, 만약 크기가 x$x$인 그룹에 x$x$가 적힌 공이 있다면 그 공은 없어진다. 조건을 만족하는 공은 모두 동시에 없어진다. 공이 없어지면 위에 있던 공들이 아래로 내려가며, 공이 없어지는 이벤트는 연쇄적으로 발생한다. 단, 크기가 n인 그룹은 크기가 n-1인 그룹을 포함하지 않는다. 즉 그룹의 가장 끝에 위치한 공은 격자의 테두리 또는 빈 공간과 인접한다.

현재 격자의 상태와 이번에 떨어뜨려야 하는 공의 번호가 주어졌을 때, 공을 한 번 떨어뜨려서 최대한 많이 공을 없애보자.

 

[입력]

첫째 줄부터 7개의 줄에 현재 격자의 상태가 주어진다. 공이 있는 칸은 공의 번호가 1부터 7까지의 숫자로 주어지며, 공이 없는 칸은 0으로 주어진다.

다음 줄에 떨어뜨릴 공의 번호가 주어진다.

게임 도중에 나타날 수 있는 상태만 입력으로 주어진다. 즉 격자의 첫 번째 줄은 모두 0이고, 공을 떨어뜨리기 전에 공이 없어지는 이벤트가 발생하지 않는 입력만 주어진다.

[출력]

공을 떨어뜨렸을 때 격자에 남아있을 수 있는 공의 개수의 최솟값을 출력한다.

 

[아이디어]

1) 다음의 단계로 구성했다.

① 행렬 transpose

② 가로, 세로 단위로 터져야 할 숫자의 위치(pop) 파악

③ 터뜨리고 오른쪽으로 shift

④ 2단계에서 pop이 있는 경우에 한해 3단계 진행을 반복

⑤ (49 - 0의 개수) 출력

 

2) 행렬의 transpose를 이용하는 이유는 세로로 숫자를 터뜨리고 이동하는 것보다 가로로 다루는 것이 더 쉽고, 개수만 파악하면 되기 때문에 전치행렬을 사용해도 관계 없기 때문이다.

3) 나는 zfill이 먼저 떠올라서 사용했는데, 그냥 리스트를 활용하면 더 쉽고 좋은 코드가 만들어지는 것 같다.

 

import copy
g = [list(input().split()) for _ in range(7)]
n = input()
gg = [list(r) for r in zip(*g)]

# drop
def drop(lst):
    i = 0
    while i<6 and lst[i+1]=='0':
        i+=1
    return i
# 가로 체크
def check_h(g,pop):
    for i in range(7):
        k = g[i].count("0")
        for j in range(7):
            # 가장 큰 덩어리의 그룹만 인식하기 위해 조건 추가
            # '단, 크기가 n인 그룹은 크기가 n-1인 그룹을 포함하지 않는다.'
            if g[i][j]!= '0' and g[i][j] == str(7 - k):
                pop.append((i,j))
    return pop
# 세로 체크
def check_v(g,pop):
    for j in range(7):
        length = 1
        i = 0
        while i<7:
            if g[i][j]=='0':
                i+=1
                continue
            while i+length<7 and g[i+length][j]!='0':
                length += 1
            for k in range(i,i+length):
                if (i==0 or g[i-1][j]=='0') and g[k][j] == str(length):
                    pop.append((k,j))
            i+=1
            length = 1
    return pop               
# 제거 및 이동
def move(gg,pop):
    nxt = []
    for i,j in pop:
        gg[i][j] = '0'
    for x in gg:
        tmp = ''
        for s in x:
            if s != '0':
                tmp += s
        nxt.append(list(tmp.zfill(7)))
    return nxt
        
answer = []
for i in range(7):
    org = copy.deepcopy(gg)
    org[i][drop(org[i])] = n
    while True:
        pop = []
        pop = check_h(org,pop)
        pop = check_v(org,pop)
        if not pop: break
        org = move(org,pop)
    num = 0
    for x in org:
        num += x.count('0')
    answer.append(49 - num)
print(min(answer))

쇼미더코드 재미삼아 신청했다가 한 문제도 못 풀고 털렸었는데, 시간이 오래 걸리긴 했지만 해결해서 기쁘다. 근데 이게 왜 골드 5,,? 난 어려운데;; 복잡한 내용은 없지만 생각하고자 하는걸 구현하는 과정에서 잔 실수를 너무 많이 해서 오래 걸렸다. '단, 크기가 n인 그룹은 크기가 n-1인 그룹을 포함하지 않는다.'의 조건을 구현하는 부분에서 많이 헤맸고, 행렬의 내용을 처음엔 int로 활용하려다 str로 활용하려 바꾸는 과정에서도 오류를 많이 내서 아쉽다.