2019 카카오 코딩테스트 - 블록게임(python)

❓ 문제 - 2019 카카오 코딩테스트 블록게임 문제 - python 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/42894)

코딩테스트 연습 - 블록 게임

 

 

📝 문제해결법 

출처 

(https://www.youtube.com/watch?v=EB8p3bHLJyU)

 

문제 해결법은 공부 목적을 위해 해당 유튜브를 참고하였고 내용을 다시 한번 정리하였습니다.

 

 

1. 문제 해결 방법은 일단 까다로운 구현이다.

2. 일단 주어진 문제에서 12가지의 블록의 종류가 존재한다.

모두 2x3 또는 3x2 모형으로 표현될 수 있다.

따라서 블록판의 모든 행과 열을 2x3 칸 또는 3x2 칸으로 돌면서 해당 블록이 지워질 수 있는지 확인한다.

 

문제에서 주어진 예시를 통해서 더 자세하게 알아보겠다.

주어진 예시를 일단 10x10 블록판에서 3x2 모형과 2x3 모형의 크기별로 모든 행과 열을 확인한다.

 

3. 모든 행과 열을 지나가면서 3x2, 2x3 모형의 크기로 돌면서 확인하는데 일단 블록을 제거할 수 있으면 count +1 해준다. 또한 블록을 제거할 수 있으면 board[row][col]값을 모두 0으로 바꿔줘서 지워버린다. 또한 모든 행과 열을 돌고 생성된 count값을 answer에 더해준다. 또한 모든 행과 열을 돌고 어떤 블록이 지워진 후에야 다른 블록이 지워질 수 있는 경우가 있으므로 무한 반복문인 while 문을 사용해서 모든 행과열을 계속 돌아준다. 또한 모든 행과열을 다 돈 후에 count값 즉, 지울 수 있는 블록의 갯수가 0이라면 더 이상 확인할 필요가 없으므로 break문을 통해서 무한루프문을 빠져나온 후 answer 값을 출력해준다.

또한 모든 행과 열을 확인하는 부분에서 <= 의 크기 제한이 있는 이유는 2x3 구간과 3x2 부분을 해당 주어진 블록판의 범위를 넘지 않으면서 확인해야하기 때문이다.

 

4. 또한 3x2, 2x3 부분에서 해당 블록을 지울 수 있는지 확인하기 위해서 find, canFill 함수를 사용한다.

1) find 함수를 통해서 일단 3x2 또는 2x3 해당 부분이 블록을 지울 수 있는지 확인한다.

일단  해당 부분이 빈 경우(블록이 안 들어있는 경우) canFill 함수를 통해서 새로운 블록이 내려와서 채워질 수 있는지 확인하고 채워질 수 없다면 블록을 지울 수 없다고 반환한다. 또한 새로운 블록을 채울 수 있다면 emptyCnt 를 +1 해준다. 하지만 해당 부분을 돌면서 emptyCnt가 2를 넘으면 False를 반환한다. 왜냐하면 해당 블록을 새로 채워서 지우기 위해서는 2칸의 새로운 블록이 필요하기 때문이다.

 

예를 들어, 다음과 같은 2x3 구간을 보는데 3칸을 채울 수 있다면 이 부분은 해당 블록이 모두 존재하는 부분이 아니기 때문에 해당 부분의 블록을 지울 수 없다고 False를 반환하는 것이다.

 

또한 해당 칸의 블록이 존재하는 경우 (0이 아닌 경우)는 lastValue 변수를 사용한다. 또한 lastValue값은 -1로 초기화해둔다. 일단 자기 블록이 존재하는 구역일수도 있으므로 확인을 위해 lastValue 값이 -1인 경우 해당 블록의 값을 저장하고, 만약 lastValue 값이 -1도 아니고 해당 블록의 값도 아닐 경우는 다른 블록과 겹쳐있는 부분이므로 False를 반환한다.

 

예를 들어 파란부분의 2x3 구간에서 해당 블록을 지울 수 있을 지 확인할 때 2행 1열의 부분에서 빨간 블록이 존재하고, 2행 2열의 부분에서는 주황 블록이 존재하므로 해당 구간에서는 블록을 지울 수 없다. 따라서 lastValue 값이 처음에 -1이 되어 있으므로 빨간블록의 값으로 다시 값이 바뀌고 다음 주황블록구간을 만날 때 해당 블록 값과 다르므로 해당 구간에 두 개 이상의 블록이 겹쳐있다고 판단할 수 있는 것이다.

 

마지막으로 모든 False로 반환될 수 있는 모든 조건에 걸리지 않으면 해당 구간에서 블록을 지울 수 있기 때문에 마지막 함수 끝나기 전에 해당 부분에서 board값을 모두 0으로 만들어서 블록을 지워버린다.

 

2) canFill 함수를 통해서 해당 칸에 새로운 블록이 위에서 부터 내려와서 쌓아질 수 있을 지 확인한다.

열은 고정시키고 행만 움직이면서 확인하는데, 확인하고 싶은 칸 위의 행에 어떠한 블록이 존재한다면 밑으로 새로운 블록이 내려갈 수 없으므로 채울 수 없다. 따라서 False를 반환한다. 

 

 

 

 

💻 소스코드 

def canFill(row, col):
    for i in range(row):
        if Board[i][col]:
            return False
    return True

def find(row, col, h, w):
    emptyCnt = 0
    lastValue = -1

    for r in range(row, row+h):
        for c in range(col, col+w):
            if Board[r][c] == 0:
                if canFill(r, c) == False:
                    return False
                emptyCnt += 1

                if emptyCnt > 2:
                    return False
            else:
                if lastValue == -1:
                    lastValue = Board[r][c]
                elif lastValue != Board[r][c]:
                    return False
    for r in range(row, row+h):
        for c in range(col, col+w):
            Board[r][c] = 0
    return True

Board = []
def solution(board):
    global Board
    Board = board
    n = len(board)
    answer = 0
    while True:
        cnt = 0
        for i in range(n):
            for j in range(n):
                if i <= n-2 and j <= n-3 and find(i, j, 2, 3):
                    cnt += 1
                elif i <= n-3 and j <= n-2 and find(i, j, 3, 2):
                    cnt += 1
        answer += cnt
        if cnt == 0:
            break
    return answer

 

🤷 느낀점

카카오 문제중에서 엄청 까다로운 구현문제인 거 같다. 알고리즘 스터디를 통해서 해설을 듣고 다시 한번 코드를 보면서 익히니깐 구현법은 그렇게 까다롭지는 않지만 이 방법을 생각하기까지 많은 노력이 들어갈 것 같다. 이러한 까다로운 구현문제들을 많이 풀어보면서 레벨 4에 해당하는 알고리즘 문제도 뿌술 수 있게 해야겠다..!!!