[알고리즘 문제] tetris (Python / 파이썬)

문제

테트리스를 해본 사람이라면 작대기 모양 테트리미노가 나오길 간절히 기다렸던 적이 있을 것이다. 지금 윤성이가 그러하다. 기다리고 기다리던 작대기 모양 테트리미노가 드디어 나온 것이다.
테트리스 맵은 가로로 C칸, 세로로 R칸의 C×R격자형 모양이다. 예를 들어보자. 아래 그림은 가로가 6칸, 세로가 6칸인 테트리스 맵의 상태이다.

(검정색 칸은 이미 메워져있던 칸이고, 회색칸은 이번에 메울 작대기 모양 테트리미노를 의미한다.)
이때 가로가 1칸이고 세로가 4칸인 1×4 직사가형 작대기 모양의 테트리미노(테트리미노는 항상 1×4)를 왼쪽에서 5번째 칸에 둘 경우 총 세줄의 수평선을 메울 수 있다. 테트리스는 한번에 여러 수평선을 메울수록 큰 점수를 얻는 게임이므로, 위 경우에서는 이 방법이 가장 높은 점수를 얻을 수 있는 방법이다.
윤성이를 도와 작대기 모양 테트리미노를 어디에 두었을 때 가장 높은 점수를 얻을 수 있는지 알려주자. (윤성이는 작대기 모양 테트리미노가 나왔을때 게임오버를 당할지언정 가로가 더 길도록 눕혀서 두지 않는다는 나름의 테트리스 철학이 있다.)
그리고 테트리스는 무조건 일자로 떨어진다. (오른쪽에서 왼쪽으로 공간을 비집고 들어가는 등의 스킬은 윤성이에겐 존재하지않는다.)

입력

첫 줄에는 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 20이다. 그다음 줄 부터 총 R줄에 걸쳐 맵의 상태를 나타내는 숫자들이 공백을 사이에 두고 주어진다. 0은 아직 채워지지 않은 칸을 나타내며 1은 채워져있는 칸을 나타낸다.

출력

작대기를 왼쪽에서 X번째 자리에 두었을 때 가장 높은 점수를 얻을 수 있고 그 때 완전히 메워지는 수평선의 개수가 Y개라면, Y를 최대로 만드는 X와 그 때의 Y를 하나의 공백을 사이에 두고 출력해야 한다.
만약 어떤 자리에 두어도 수평선을 하나도 메울 수 없거나 게임오버가 일어나는 경우라면 X와 Y를 둘다 0으로 출력한다.(게임오버는 새로 내려온 작대기가 맵상을 벗어난 경우에 일어난다. 새로나온 작대기가 맵의 가장자리에 걸쳐있는 경우는 게임오버가 아니다.)

---

문제 풀이

테트리스 문제는 왼쪽에서 몇 번째 칸에 1x4 직사각형 테트리미노를 두었을 때 

수평선을 가장 많이 메울 수 있는지 구하는 문제이다. 

 

따라서 왼쪽부터 각 열에 테트리미노를 두어보고 

둘 때마다 수평선을 몇개 메울 수 있는지 구해주면 된다. 

이때 주의해야할 점은 테트리미노를 열에서 어디에 두어야 하는지 구하는 것이다.

만약 이미 채워져 있는 칸이라면 테트리미노를 둘 수 없다. 

따라서 이미 채워져 있는 칸의 제일 위보다 한칸 위부터 테트리미노를 두어야 한다. 

만약 채워져 있는 칸이 없다면 자동으로 테트리미노는 맨 아래로 간다. 

이러한 점을 이용해 테트리미노의 제일 아래 칸의 위치를 구해준다. 

 

만약 구한 위치가 3보다 작다면 테트리미노를 둘 수 없다는 뜻이다. 

따라서 이러한 경우에는 다음 열로 넘어가도록 해준다. 

만약 테트리미노를 둘 수 있다면 둘 수 있는 위치를 모두 1로 바꿔준다. 

그런 다음 메울 수 있는 수평선의 개수를 세어준다. 

수평선의 개수를 센 뒤 다음 탐색을 위해 테트리미노를 둔 위치를 다시 0으로 바꿔줘야한다. 

 

수평선의 개수는 각 행에서 1인 원소들을 세어주고 만약 

1인 원소들의 개수가 열의 개수와 같다면 수평선의 개수를 세어주면 된다. 

이렇게 각 열에서 테트리미노를 두었을 때 수평선의 개수를 구한 뒤

그 중 최대값을 구해주면 된다. 

---

My Code

 

# 수평선의 개수를 확인하는 함수
def check():
    result = 0
    # 각 행을 탐색 
    for i in range(n):
        count = 0
        for j in range(m):
            if board[i][j] == 1:
                count += 1
        if count == m: # 1인 원소가 열의 개수와 같다면
            result += 1 # 수평선의 개수 세어줌

    return result

m, n = map(int,input().split()) # 격자의 가로, 세로 크기

# 격자의 초기 상태
board = []
for _ in range(n):
    board.append(list(map(int,input().split())))

total = 0
index = 0
for j in range(m): # 각 열에서 탐색
    now = n - 1  # 아무것도 채워져있지 않다면 맨 아래부터 채움

    for i in range(n): 
        if board[i][j] == 1: # 채워진게 있다면
            now = i - 1      # 그 위부터 채움
            break            

    if now < 3: continue # 테트리미노의 제일 아래가 3보다 작으면 채울 수 없음

    for i in range(4):
        board[now - i][j] = 1 # 테트리미노를 채워줌

    if total < check():  # 수평선의 개수를 구해 최대값 구해줌
        total = check()
        index = j + 1    # 최대일 때의 열의 번호

    for i in range(4):
        board[now - i][j] = 0 # 채운 테트리미노를 지워줌

print(index, total)