20061 - 모노미노도미노 2

 

---

 

문제

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

20061번: 모노미노도미노 2

 

풀이

해당문제는 총 3개의 큰 로직으로 나눠서 구현할 수 있다. (설명은 파란 보드를 기준으로 모두 한다.)

 

1. 이동 로직
   • for문으로 보드를 순회하면서 블록을 설치할 수 있는지 없는지 판단한다.
     • 특정 위치에 블록이 있다면, 그 전 위치에 블록을 위치해주면 된다.
     • 만약 끝까지 갔는데도 없으면, 마지막 위치에 블록을 위치한다.
2. 줄을 지우고, 앞선 줄을 당기는 로직
   • 블록이 최종위치에 안착했다면, 해당 줄을 검사한다. 만약 꽉 차 있다면, 앞선 줄들을 한칸씩 당겨주면 된다.
   • 0번 인덱스는 앞에 값이 없으니 예외처리 해줘야한다. (0으로 다 채우면 됨)
   • 해당 로직은 줄 하나를 잡아서 반복적으로 처리함으로, 당겨온 줄이 다시 지워질 수 있는 상황도 대비한다.
   • 단 1 * 2 블록은 제거해야하는 줄을 잘 처리해줘야한다. 1 * 1 이나 2 * 1 은 모두 세로로 한 줄 이기에 지워지는 줄이 무조건 하나로 특정되지만, 1 * 2 는 가로로 두 줄이기때문에 앞쪽이 지워질수도, 뒷쪽이 지워질수도 있다. 따라서 줄을 2개 검사해야한다.

해당 블록이 멈추는 파란보드 1열이 가득차 있는지 검사한다. 만약 모두 차있으면 해당 열을 기준으로 앞쪽 값들을 당겨주고, 지울게 없을때까지 로직을 반복한다.

 

1 * 2 블록같은 경우에는 검사해야할 줄이 2줄임을 잊지말자. 오른쪽이 지워지면서 앞으로 땡겨지면 끝줄만 검사해도 큰 문제는 없으나, 왼쪽만 지워지는 경우가 있기 때문에.

3. 옅은 부분에 블록이 존재하는지 확인

• 이 로직은 단순하다, 옅은 부분에 값이 하나라도 있으면 한칸씩 모두 당겨주면 된다. 이 또한 인덱스가 0 일때는 0으로 모두 채워주는 예외 처리를 해줘야한다.

 

로직은 이렇게 흘러간다, 설명은 파란색 기준으로 했지만 초록색도 원론적으론 같으니 말이다.

 

그래서 나는 몇가지의 처리를 함으로써 파란색, 초록색 처리를 하나의 함수로 구현했다.

 

이렇게 돌려서 생각했음

 

위 사진처럼 파란색 보드처럼 처리했고, 규칙성을 찾아봤다.

 

오리지널 값	초록 보드에 적용되는 값	적용범위
[2, 0, 1]	[3, 2, 0]	(x ~ x-1), y
[3, 1, 0]	[2, 3, 1]	x, (y ~ y+1)
[2, 2, 2]	[3, 1, 2]	(x ~ x-1), y

 

우선 가로 세로를 바꿔줘야한다. 2일때는 3, 3일때는  2

그리고 행과 열이 변경되는데 행같은 경우에는 그 값 그대로 열로 이동하면 된다.

열같은 경우에는 값이 반대로 되므로, 0->3, 1->2, 2->1, 3->0 이런식으로 변환시켜서 저장하면 된다.

 

단 초록보드에 세로블록이 적용될때는 x, x+1이 아니라, x ~ x-1 공간을 차지한다. 따라서 x를 -1 해주면 똑같은 로직으로 처리가 가능하다.

 

 

코드

from sys import stdin

def chagne(v):
    if v == 0 : return 3
    if v == 1 : return 2
    if v == 2 : return 1
    if v == 3 : return 0

def setPositionForGreen(x, y):
    x, y = y, x
    x = chagne(x)
    return x, y

def setValuesForGreen(t, x):
    if t == 2:
        return 3, x-1
    if t == 3:
        return 2, x
    return t, x

def solution(color, val, area):
    global answer
    t, x, y = val
    if color == 'green':
        x, y = setPositionForGreen(x, y)
        t, x = setValuesForGreen(t, x)

    isInstall = -1

    for i in range(6):
        # 1 * 1 block
        if t == 1:
            if area[x][i] != 0:
                area[x][i - 1] = 1
                isInstall = i - 1
                break
            # at the end of the range
            if i == 5:
                area[x][i] = 1
                isInstall = i
                break

        # 1 * 2 block (width)
        if t == 2:
            if i < 5 and area[x][i + 1] != 0:
                area[x][i] = 1
                area[x][i - 1] = 1
                isInstall = i
                break
            if i == 4:
                area[x][i] = 1
                area[x][i + 1] = 1
                isInstall = i+1
                break

        # 2 * 1 block (height)
        if t == 3:
            if area[x][i] != 0 or area[x + 1][i] != 0:
                area[x][i - 1] = 1
                area[x + 1][i - 1] = 1
                isInstall = i - 1
                break
            if i == 5:
                area[x][i] = 1
                area[x + 1][i] = 1
                isInstall = i
                break

    # check and remove Logic
    while True:
        cnt = 0
        for i in range(4):
            if area[i][isInstall] != 0:
                cnt += 1

        # need to remove and pull
        if cnt == 4:
            answer += 1
            for j in range(isInstall, -1, -1):
                for k in range(4):
                    if j == 0:
                        area[k][j] = 0
                    else:
                        area[k][j] = area[k][j - 1]

        # if there's no more line to remove
        else:
            if t == 2 and isInstall != 0:
                isInstall -= 1
                continue
            break

    # ligth block area Logic
    while True:
        move = False
        for j in range(4):
            if area[j][1] != 0:
                move = True
                break

        if not move:
            return area

        for j in range(5, -1, -1):
            for k in range(4):
                if j == 0 :
                    area[k][j] = 0
                else:
                    area[k][j] = area[k][j - 1]

n = int(input())
blocks = []
for _ in range(n):
    blocks.append(list(map(int, stdin.readline().rstrip().split())))

greenArea = [[0] * 6 for _ in range(4)]
blueArea = [[0] * 6 for _ in range(4)]

answer = 0

for block in blocks:
    blueArea = solution('blue', block, blueArea)
    greenArea = solution('green', block, greenArea)

total = 0
for i in range(4):
    for j in range(6):
        if greenArea[i][j] != 0:
            total += 1
        if blueArea[i][j] != 0:
            total += 1

print(answer)
print(total)

 

후기

 

복잡한 문제였다. 그래도 하나의 함수로 두 공간을 깔끔히 처리한 거 같아 뿌듯하다.