[BOJ 19235] 모노미노도미노 - Python

Algorithm

시뮬레이션, 구현

Logic

접근법 -> green map을 blue map 처럼 만들어서 따로 구현하지 않고 한꺼번에 한다 !

모노미노도미노 map은 이러한 모양을 가지는데, 이 때 우리가 필요한 정보는 초록색 map과 파란색 map이다. 빨간색 map은 y, x만 알면 되기 때문에 굳이 배열로 만들지 않아도 된다.

대부분의 풀이가 greenMap과 blueMap 각각을 따로 구현했던데, 나는 greenMap을 blueMap 모양으로 만들어서 함수 하나로 다 풀 수 있도록 했다.

이 때 주의할 점:

redMap의 행 기준으로 blueMap 블럭을 민다

redMap의 열 기준으로 greenMap 블럭을 민다

 

기본적으로 새로운 블럭을 놓을 위치를 찾는 구현은 blueMap 기준으로 했고, greenMap을 파라미터로 넣을 때는 기준 Line과 블럭 모양을 바꿔줘야한다.

 

블럭모양은

순서대로 1, 2, 3번 블럭

세가지로 주어지는데, 이 때 생각해줘야하는 부분은 두 가지 line을 걸치고 움직이는 블럭이다. (blueMap 기준으로는 3번, greenMap 기준으로는 2번)

근데 greenMap을 뒤집었기 때문에 블럭 순서도 (1, 3, 2)번으로 해주면 blueMap과 똑같이 구현가능하다.

# blue와 green 모두 같은 모양의 배열로 만듦
blue = [[0 for _ in range(6)] for _ in range(4)]
green = [[0 for _ in range(6)] for _ in range(4)]

# greenMap으로 블럭을 내릴 때 블럭모양을 변경해줘야하므로
changeType = [0, 1, 3, 2]

# greenMap을 뒤집음으로써 같은 함수로 다 구현이 가능하다
# 블럭 이동
moveBlock(blue, type, x)
moveBlock(green, changeType[type], y)

# 한 라인에 블럭이 가득찬다면, 그 줄을 삭제
removeLine(blue)
removeLine(green)

# 특별한 칸에 블럭이 쌓였다면, 이를 처리해주는 함수
specialLine(blue)
specialLine(green)

# 위의 과정 후 다시 한 라인에 블럭이 가득찼을 수도 있으므로 한번 더 확인
removeLine(blue)
removeLine(green)

 

- moveBlock 함수

def moveBlock(map, type, standard):
    flag = False
    if type == 1:  # 1x1
        for i in range(6):
            if map[standard][i] != 0:
                flag = True
                break
        if not flag:
            map[standard][i] = type
        else:
            map[standard][i - 1] = type

    elif type == 2:  # 1x2
        for i in range(6):
            if map[standard][i] != 0:
                flag = True
                break
        if not flag:
            map[standard][i - 1] = type
            map[standard][i] = type
        else:
            map[standard][i - 2] = type
            map[standard][i - 1] = type

	# 두 줄을 걸치고 내려오는 경우
    elif type == 3:  # 2x1
        for i in range(6):
        	# 두 줄을 모두 확인하면서 블럭을 쌓을 수 있는 곳을 찾음
            for j in range(standard, standard + 2):
                if map[j][i] != 0:
                    flag = True
                    break
            if flag:
                break
        if not flag:
            map[standard][i] = type
            map[standard + 1][i] = type
        else:
            map[standard][i - 1] = type
            map[standard + 1][i - 1] = type

 

- removeLine 함수

def removeLine(map):
    global score

	# 라인을 삭제한 후에 또 삭제할 라인이 생길 수 있으므로 while문으로 확인해주어야 함
    while True:
        flag = False
        maxRow = 0
        for i in range(6):
            count = 0
            for j in range(4):
                if map[j][i] > 0:
                    count += 1
            if count == 4:  # 지우기
                maxRow = max(maxRow, i)
                score += 1
                flag = True
                for j in range(4):
                    map[j][i] = 0
        if not flag:
            break
        removeEmptySpace(map, maxRow)

 

- specialLine 함수

def specialLine(map):
    line0Cnt = 0
    line1Cnt = 0

    for j in range(4):
        if map[j][0] != 0:
            line0Cnt += 1

    for j in range(4):
        if map[j][1] != 0:
            line1Cnt += 1

    if line1Cnt > 0 and line0Cnt > 0:  # 오른쪽 두 칸 비우기
        for i in range(4):
            map[i][5] = 0
            map[i][4] = 0
        removeEmptySpace(map, 3)

    elif line1Cnt > 0 and line0Cnt == 0:  # 오른쪽 한 칸 비우기
        for i in range(4):
            map[i][5] = 0
        removeEmptySpace(map, 4)

 

- removeEmptySpace 함수: line을 삭제한 후 사이에 생긴 빈 공간을 없애주는 함수

확인을 시작할 row(maxRow)부터 index를 줄여가면서 본다. 

블럭 type이 1이거나 2이면, 그냥 빈칸 생긴 부분을 다 없애주면 되는데, type이 3인 경우는 그렇게 하면 안된다. 블럭이 두 line을 걸쳐있기 때문에, 두 line 중 하나라도 다른 블럭을 만난다면(더 이상 빈 공간이 없다면) 그때 그만해야된다.

def removeEmptySpace(map, maxRow):
    for i in range(maxRow, -1, -1):
        for j in range(3, -1, -1):
            if map[j][i] == 2 or map[j][i] == 1:
                new = i + 1
                while new < 6 and map[j][new] == 0:
                    map[j][new] = map[j][new - 1]
                    map[j][new - 1] = 0
                    new = new + 1
            elif j < 3 and map[j][i] == 3 and map[j + 1][i] == 3:
                new = i + 1
                while new < 6 and map[j][new] == 0 and map[j + 1][new] == 0:
                    map[j][new] = 3
                    map[j + 1][new] = 3
                    map[j][new - 1] = 0
                    map[j + 1][new - 1] = 0
                    new = new + 1

Review

걸린 시간: 2시간 20분 + a ..

처음 구현은 2시간 20분만에 다 했는데 제출하니까 0%에서 아예 틀렸다고 뜨는 것이다..

게시판에 반례도 다 돌려보는데 다 맞게 나와서 멘붕왔다..

다른 사람들 풀이봐도 모르겠구,,, 다시 처음부터 코드 꼼꼼히 읽는데 실수를 두 군데를 해서 안됐었다

하필 그 실수를 한 부분이 

1. 빈 공간 줄여주는 곳에서 new 변수를 업데이트를 안해서 한 번만 줄여주게 됐다

2. specialLine 함수에서 특별한 칸에 블럭이 위치하지 않을 때도 removeEmptySpace 함수를 호출

 

그래서 1번 때문에 빈 공간을 덜 줄여줬는데도 removeEmptySpace를 여러번 더 불러서 결국 빈 공간은 다 줄여졌고, 테스트케이스가 다 맞게 나온 것이다....

흑흑

 

Code

def moveBlock(map, type, standard):
    flag = False
    if type == 1:  # 1x1
        for i in range(6):
            if map[standard][i] != 0:
                flag = True
                break
        if not flag:
            map[standard][i] = type
        else:
            map[standard][i - 1] = type

    elif type == 2:  # 1x2
        for i in range(6):
            if map[standard][i] != 0:
                flag = True
                break
        if not flag:
            map[standard][i - 1] = type
            map[standard][i] = type
        else:
            map[standard][i - 2] = type
            map[standard][i - 1] = type

    elif type == 3:  # 2x1
        for i in range(6):
            for j in range(standard, standard + 2):
                if map[j][i] != 0:
                    flag = True
                    break
            if flag:
                break
        if not flag:
            map[standard][i] = type
            map[standard + 1][i] = type
        else:
            map[standard][i - 1] = type
            map[standard + 1][i - 1] = type


def removeEmptySpace(map, maxRow):
    for i in range(maxRow, -1, -1):
        for j in range(3, -1, -1):
            if map[j][i] == 2 or map[j][i] == 1:
                new = i + 1
                while new < 6 and map[j][new] == 0:
                    map[j][new] = map[j][new - 1]
                    map[j][new - 1] = 0
                    new = new + 1
            elif j < 3 and map[j][i] == 3 and map[j + 1][i] == 3:
                new = i + 1
                while new < 6 and map[j][new] == 0 and map[j + 1][new] == 0:
                    map[j][new] = 3
                    map[j + 1][new] = 3
                    map[j][new - 1] = 0
                    map[j + 1][new - 1] = 0
                    new = new + 1

def removeLine(map):
    global score

    while True:
        flag = False
        maxRow = 0
        for i in range(6):
            count = 0
            for j in range(4):
                if map[j][i] > 0:
                    count += 1
            if count == 4:  # 지우기
                maxRow = max(maxRow, i)
                score += 1
                flag = True
                for j in range(4):
                    map[j][i] = 0
        if not flag:
            break
        removeEmptySpace(map, maxRow)


def specialLine(map):
    line0Cnt = 0
    line1Cnt = 0

    for j in range(4):
        if map[j][0] != 0:
            line0Cnt += 1

    for j in range(4):
        if map[j][1] != 0:
            line1Cnt += 1

    if line1Cnt > 0 and line0Cnt > 0:  # 오른쪽 두칸 비우기
        for i in range(4):
            map[i][5] = 0
            map[i][4] = 0
        removeEmptySpace(map, 3)

    elif line1Cnt > 0 and line0Cnt == 0:  # 오른쪽 한칸 비우기
        for i in range(4):
            map[i][5] = 0
        removeEmptySpace(map, 4)



N = int(input())
blue = [[0 for _ in range(6)] for _ in range(4)]
green = [[0 for _ in range(6)] for _ in range(4)]
changeType = [0, 1, 3, 2]
score = 0
blue_cnt = 0
green_cnt = 0
# i = x, j = y
for n in range(N):
    type, x, y = map(int, input().split())

    moveBlock(blue, type, x)
    moveBlock(green, changeType[type], y)

    removeLine(blue)
    removeLine(green)

    specialLine(blue)
    specialLine(green)

    removeLine(blue)
    removeLine(green)

for i in range(4):
    blue_cnt += blue[i].count(0)
    green_cnt += green[i].count(0)

print("{}\n{}".format(score, 4 * 6 - blue_cnt + 4 * 6 - green_cnt))