Lv3 프로그래머스 퍼즐 조각 채우기 풀이 과정 (Swift)

개요

여느 때 처럼 코딩테스트 준비를 위해 프로그래머스를 풀던 중, 거의 이틀을 머리 아프게 만든 문제를 발견습니다.

너무나도 어렵고, 써야 하는 코드도 방대했지만 꽤나 재밌고 뿌듯했던 풀이 과정을 정리해 보려고 합니다.

(+ 혹시나 누군가에겐 도움이 될 수도 있으니..!)

참고로 보완이 많이 필요한 코드입니다. 우선 풀이 과정을 적고 추후 더 디벨롭을 해 보기로..!

 

문제 분석

우선 이 문제는, 프로그래머스 고득점 Kit 모음의 DFS/BFS 카테고리에 속해 있고 Level 3이라 제겐 굉장히 고난이도인 문제였습니다.

 

문제: 퍼즐 조각 채우기

요약

왼쪽의 game_board의 빈 칸에 오른쪽 table에 있는 퍼즐 조각을 최대한 많이 넣어서, 총 몇 칸을 채울 수 있는지를 리턴하는 문제.

 

조건

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다

특히 마지막 조건 때문에 굉장히 까다로웠던 것 같습니다.

 

풀이 예상해 보기

아래는 제가 문제를 풀기 전 대략 그려본 큰 흐름 입니다.

꽤 복잡한 문제이기 때문에 미리 공책으로 이리저리 생각해 보지 않았다면 풀기 어려웠을 것 같아요.

 

1. 제일 먼저 0과 1로만 되어 있는 table 배열에서 퍼즐 조각들을 식별하자
2. 그리고 퍼즐 조각들을 실제로 덩어리로 분리하자
3. 퍼즐 조각들을 회전해 가면서 퍼즐 조각들을 game_board에 맞춰 보자

1번에서는 dfs/bfs 를 사용할 수 있을 것 같고, 2번에서는 비교할 수 있을 작은 배열로 만들 수 있을 것 같았습니다.

3번에서는 배열을 회전하는 법, 전체 game_board 와 작은 퍼즐 배열을 비교하는 법을 찾아내는 것이 관건이라고 생각했습니다.

 

실제 풀이 과정

1) table 배열에서 퍼즐 조각들을 식별하기

제일 먼저 table 배열에서 퍼즐 조각들을 식별합니다.

사실 근본 없는 야매 개발자로서 저는.. 제가 푼 방법이 확실히 dfs인지 확신이 없긴 하지만

stack을 사용해서 퍼즐을 식별할 때 까지 파고들었으니 dfs라고 생각..합니다..!

 

table의 모든 칸들을 돌면서 퍼즐 조각을 탐색합니다.

• 이 때, 칸이 비어있거나 (퍼즐 조각의 일부가 아님) 이미 방문한 칸이라면 (이미 퍼즐 조각으로 식별됨) 패스합니다.
• 반면 칸이 차 있는 경우 (퍼즐 조각의 일부인 경우) 에는 상/하/좌/우로 연결된 퍼즐 조각의 일부가 있는지 확인 후 있다면 해당 칸을 탐색할 수 있도록 stack에 넣습니다.
• stack에서 꺼내진 요소들(퍼즐 조각에 해당하는 index들)은 piece라는 배열에 넣음으로써 퍼즐 조각을 식별합니다.

 

즉 정리하자면,

• stack에 들어가는 요소들 → 퍼즐 조각의 일부이며 탐색할 대상
• piece에 들어가는 요소들 → 이미 탐색이 완료되어 퍼즐 조각의 일부로 식별된 인덱스
• while 문이 종료되고 나면 (stack이 비었다면) → 퍼즐 조각 하나가 식별됨
• for 문이 종료되고 나면 → 모든 퍼즐 조각들이 식별됨

 

이런 과정이라고 볼 수 있습니다.

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // 전체 테이블의 크기
    var n = table.count
    
    // table에서 퍼즐 조각을 탐색한다
    var pieces = [[(Int, Int)]]() // 퍼즐 조각들을 담아놓을 곳
    var visited = Array(repeating: Array(repeating: false, count: n), count: n) // 방문 여부를 체크할 곳
    
    // table을 돌면서
    for i in 0..<table.count {
        for j in 0..<table.count {
            // 퍼즐이 없거나 이미 방문했다면 패스~
            if table[i][j] == 0 || visited[i][j] { continue }
            
            var stack = [(i, j)]    // 새로 탐색할 퍼즐이 들어가는 곳
            var piece = [(Int, Int)]()  // 퍼즐 조각들이 쌓이는 곳
            while !stack.isEmpty {
                var (a, b) = stack.removeFirst()
                visited[a][b] = true
                piece.append((a, b))
                
                // 상하좌우 확인 후 스택에 넣기
                let search = [(a-1, b), (a+1, b), (a, b-1), (a, b+1)]
                for (x, y) in search {
                    if x < 0 || y < 0 || x >= n || y >= n { continue }
                    if visited[x][y] || table[x][y] == 0 { continue }
                    stack.append((x, y))
                }
            }
            
            // 여기는 전체 퍼즐들이 모이는 곳
            pieces.append(piece)
        }
    }
    
    // ...


    return count
}

 

2) ‘모든 퍼즐에 대해’ 퍼즐 조각들을 작은 배열(덩어리)로 만들기

먼저 언급하자면, 제 코드에는 반복문이 굉장히 많이 등장합니다.

그래서 반복문의 흐름을 한 번 더 정리하면 좋을 것 같습니다.

 

💡 앞선 퍼즐을 식별한 그 후의 과정

 

반복문 1) 모든 퍼즐에 대해

반복문 2) 모든 모양(회전)에 대해

반복문 3) 모든 game_board의 빈 자리에 대해

 

퍼즐이 들어갈 수 있는 자리를 탐색합니다.

 

따라서 지금은 반복문 1) 모든 퍼즐에 대해 반복문을 수행하면서, 해당 퍼즐들을 작은 배열로 만드는 과정에 있습니다.

 

그리고 그 과정은 아래와 같습니다.

• 퍼즐의 인덱스들의 최소, 최댓값을 활용하여 너비와 높이를 알아냅니다.
• 그리고 퍼즐의 틀이 될 배열을 생성합니다.
• 마지막으로 실제 퍼즐 정보를 반영합니다.

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // ...
    
    var game_board_copy = game_board
    var count = 0

    // 반복문 1)
    // 퍼즐 조각들(을 나타내는 인덱스들)을 돌면서
    for piece in pieces {
        // 퍼즐의 크기 식별
        let sorted1 = piece.sorted{$0.1 < $1.1}
        let sorted2 = piece.sorted{$0.0 < $1.0}
        let width = sorted1.last!.1 - sorted1.first!.1 + 1
        let height = sorted2.last!.0 - sorted2.first!.0 + 1
        
        // 퍼즐 조각들을 실제 퍼즐(배열)으로 만들기 위한 배열(틀) 생성
        var pieceArray = Array(repeating: Array(repeating: 0, count: width), count: height)

        // 실제로 반영
        for (i, j) in piece {
            pieceArray[i-sorted2[0].0][j-sorted1[0].1] = 1
        }
            
        // ...
        
    }
    // 반복문 1)


    return count
}

 

3) ‘모든 퍼즐에 대해’ 배열을 90도 회전시키기

문제의 조건을 보면 퍼즐을 회전시킬 수 있습니다.

따라서 퍼즐이 game_board의 빈 칸에 맞지 않다면 퍼즐을 회전시켜 시도해 보아야 합니다.

 

4가지 회전의 경우가 있습니다.

0도(360도), 90도, 180도, 270도 입니다.

 

2차원 배열을 90도를 회전하게 되면 규칙이 있습니다.

row는 column 값으로 그대로 교체되고, column 값은 row 인덱스의 반대값(최솟값이면 최댓값..)이 됩니다.

따라서 이 규칙을 활용해 turn 함수를 구현하고, 이를 반복해서 사용했습니다.

 

그리고 이제는 반복문 2) 모든 모양(회전)에 대해 탐색을 시작합니다.

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // ...
    
    // 퍼즐을 90도로 돌리는 함수
    func turn(_ w: Int, _ h: Int, _ originalArray: [[Int]]) -> [[Int]] {
        var tempArray = Array(repeating: Array(repeating: 0, count: h), count: w)
        for i in 0..<h {
            for j in 0..<w {
                if originalArray[i][j] == 1 {
                    tempArray[j][h-i-1] = 1
                }
            }
        }

        return tempArray
    }
    
    // ...
    
    // 반복문 1)
    // 퍼즐 조각들(을 나타내는 인덱스들)을 돌면서
    for piece in pieces {
        // ...
            
        // 90도, 180도, 270도로 회전시키기
        var turned90 = turn(width, height, pieceArray)
        var turned180 = turn(height, width, turned90)
        var turned270 = turn(width, height, turned180)
        
        var allAngles = [pieceArray, turned90, turned180, turned270]
        var stopLoop = false

        // 반복문 2)
        // 모든 모양(퍼즐)을 가지고 game_board 에 맞추어 본다
        for angle in allAngles {
            // ...
        }
        // 반복문 2)
        
    }
    // 반복문 1)


    return count
}

 

4) ‘모든 game_board의 빈 자리에 대해’ 비교할 배열 만들기

이제는 반복문 3) 모든 game_board의 빈 자리에 대해 퍼즐을 탐색할 차례입니다.

 

우선 퍼즐 조각들을 실제 game_board와 비교할 수 있도록 game_board를 부분 배열인 subArray로 만들어 보겠습니다.

이 때 중요한 것은 단순히 퍼즐 부분만 비교하는 것이 아니라, 인접한 부분이 비어 있지 않다는 것도 확인해야 한다는 것입니다. (조건 만족)

• 따라서 퍼즐 조각보다 한 겹이 더 커진 배열(틀)을 만듭니다
• 퍼즐 조각의 최상단은 현재 game_board의 row, column 인덱스가 되도록 합니다
  • i == row, j == column이 되어야 하기 때문에 subArray[i-row+1][j-column+1] = 1

   

• 만약 퍼즐 말고 인접한 부분이 game_board 배열을 벗어나면 채워진 것으로 처리합니다

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // ...

    // 반복문 1)
    // 퍼즐 조각들(을 나타내는 인덱스들)을 돌면서
    for piece in pieces {
        // ...
        
        // 반복문 2)
        // 모든 모양(퍼즐)을 가지고 game_board 에 맞추어 본다
        for angle in allAngles {
            // 퍼즐의 크기
            let h = angle.count, w = angle[0].count

            // 반복문 3) (3-1, 3-2)
            // 모든 game_board의 빈 자리에 대해 비교한다
            for row in 0..<n {
                for column in 0..<n {
                    // 비교할 수 있게 배열(틀)을 하나 만든다
                    var subArray = Array(repeating: Array(repeating: 0, count: w+2), count: h+2)
                    
                    // 안의 내용을 채운다
                    // (내부 반복문 - 1)
                    for i in row-1...row+h {
                        for j in column-1...column+w {
                            if (i >= 0 && j >= 0 && i < n && j < n) {
                                // 퍼즐이 들어갈 수 없는 자리라면
                                if game_board_copy[i][j] == 1 {
                                    // 1로 설정
                                    subArray[i-row+1][j-column+1] = 1
                                }
                            } else {
                                // 만약에 배열을 벗어나도 1로 설정
                                subArray[i-row+1][j-column+1] = 1
                            }
                        }
                    }
                    // (내부 반복문 - 1)
                    
                    // ...
                    
                }
            }
            // 반복문 3) (3-1, 3-2)
            
        }
        // 반복문 2)
        
    }
    // 반복문 1)


    return count
}

 

5) ‘모든 game_board의 빈 자리에 대해’ 실제 비교할 퍼즐 배열 (인접한 부분 포함) 만들기

위에서 보았듯 중요한 것은 단순히 퍼즐 부분만 비교하는 것이 아니라, 인접한 부분이 비어 있지 않다는 것도 확인해야 한다는 것입니다. (조건 만족)

사실 처음엔 단순히 퍼즐만 비교해서 빈 칸에 맞춰지는지만 비교했다가, 조건의 존재를 깨닫고 굉장히 절망했던 기억이 납니다. 문제 조건을 잘 봐야 한다는 교훈..

 

아무튼 그래서 조건을 만족하기 위해 - 1) 인접한 칸들까지 표시하기 위해 배열 확장, 2) 인접한 칸들 식별 및 처리, 3) 실제 비교 - 이렇게 새로운 계획을 세웠습니다.

여기서 인접한 칸들을 어떻게 식별할 지가 막막했는데 생각보다 방법은 간단했습니다.

 

💡 퍼즐과 인접한 칸들을 식별하는 법

 

안쪽의 빈 Z..? 모양은 퍼즐을 의미합니다. 그리고 반드시 비어있으면 안되는 인접한 칸들을 연필로 칠해 보았습니다. 이렇게 그림을 그리고 색을 칠하고 나니, 엇 이거 퍼즐 상하좌우로 움직이면 되는구나..? 하고 깨달았습니다.

 

아무튼 그래서 저는 퍼즐을 상하좌우로 움직여 가면서 인접한 부분을 식별하였습니다.

그래서 처음은 퍼즐이 빈 상태 (모두 0) → 상하좌우로 움직이며 채워진 모든 부분을 -1로 바꾸고 → 마지막으로 실제 퍼즐 부분만 1로 변경하는 방식으로 하였습니다.

 

그리고 만약 퍼즐을 game_board에 끼워넣는 데 성공하면 채워진 칸을 더해주어야 하기에, blockCount를 미리 계산해 주었습니다.

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // ...

    // 반복문 1)
    // 퍼즐 조각들(을 나타내는 인덱스들)을 돌면서
    for piece in pieces {
        // ...

        // 반복문 2)
        // 모든 모양(퍼즐)을 가지고 game_board 에 맞추어 본다
        for angle in allAngles {
            // ...

            // 반복문 3) (3-1, 3-2)
            // 모든 game_board의 빈 자리에 대해 비교한다
            for row in 0..<n {
                for column in 0..<n {
                    // ...
                    
                    // 인접한 부분 만들기 위해 빈 배열에
                    var largerArray = Array(repeating: Array(repeating: 0, count: w+2), count: h+2)
                                        
                                        // (내부 반복문 - 2)
                    // 인접, 안쪽 모두 1로 채워넣고
                    for i in 0..<h {
                        for j in 0..<w {
                            if angle[i][j] == 1 {
                                // 상, 하, 좌, 우
                                largerArray[i][j+1] = -1
                                largerArray[i+2][j+1] = -1
                                largerArray[i+1][j] = -1
                                largerArray[i+1][j+2] = -1
                            }
                        }
                    }
                    // (내부 반복문 - 2)
                                        
                    // (내부 반복문 - 3)
                    // 실제 퍼즐 부분만 1로 다시 처리하기
                    var blockCount = 0
                    for i in 0..<h {
                        for j in 0..<w {
                            if angle[i][j] == 1 {
                                largerArray[i+1][j+1] = 1
                                blockCount += 1
                            }
                        }
                    }
                    // (내부 반복문 - 3)

                    // ...
                    
                }
            }
            // 반복문 3) (3-1, 3-2)

        }
        // 반복문 2)
        
    }
    // 반복문 1)


    return count
}

 

6) ‘모든 game_board의 빈 자리에 대해’ 실제 퍼즐 비교하기

이제 마지막 과정입니다.. subArray와 largerArray를 비교합니다.

• 퍼즐 조각은 subArray의 빈 자리에 들어갈 수 있어야 합니다.
• 퍼즐의 인접한 부분은 비어 있지 않아야 합니다.
• 위 조건들을 만족하지 않으면 퍼즐이 들어갈 수 없습니다.

 

만약 모든 퍼즐 조각들이 통과했으면 count와 game_board_copy를 업데이트 하고, 반복문을 종료합니다.

count는 지금까지 채워진 칸의 수, game_board_copy는 지금까지 채워진 퍼즐들을 포함한 game_board 배열입니다.

 

여러 겹으로 중첩된 반복문들을 탈출하기 위해 Bool 값을 계속 활용하였는데, 별로 좋지 않은 방식인 것 같아 추후에는 꼭 보완하고 싶네요..ㅠ

 

아무튼 이렇게 해서 프로그래머스 퍼즐 조각 채우기 문제를 통과했습니다..!

 

풀이 코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {

    // ...

    // 반복문 1)
    // 퍼즐 조각들(을 나타내는 인덱스들)을 돌면서
    for piece in pieces {
        // ...

        // 반복문 2)
        // 모든 모양(퍼즐)을 가지고 game_board 에 맞추어 본다
        for angle in allAngles {
            // ...

            // 반복문 3) (3-1, 3-2)
            // 모든 game_board의 빈 자리에 대해 비교한다
            for row in 0..<n {
                for column in 0..<n {
                    // ...

                    // subArray와 largerArray의 비교
                    var blockCanFit = true
                    var boardVisited = game_board_copy
                    
                    // (내부 반복문 - 4)
                    for i in 0..<h+2 {
                        for j in 0..<w+2 {
                            if largerArray[i][j] == 1 {
                                if subArray[i][j] == 1 {
                                    // 퍼즐이 들어가야 하는데 이미 차 있다
                                    blockCanFit = false
                                    break
                                } else {
                                    // 퍼즐이 들어갈 수 있다
                                    boardVisited[i+row-1][j+column-1] = 1
                                }
                            } else if largerArray[i][j] == -1 {
                                if subArray[i][j] == 0 {
                                    // 주변 공간은 이미 채워져 있어야 하는데 비어 있다
                                    blockCanFit = false
                                    break
                                }
                            }
                        }
                        
                        if !blockCanFit {
                            break
                        }
                    }
                    // (내부 반복문 - 4)

                    // 퍼즐이 통과했으면 count와 game_board_copy를 업데이트 하고, 반복문 종료
                    if blockCanFit {
                        count += blockCount
                        game_board_copy = boardVisited
                        stopLoop = true
                        break
                    }
                    
                }
                
                if stopLoop {
                    break
                }
                
            }
            // 반복문 3) (3-1, 3-2)
            
            if stopLoop {
                break
            }

        }
        // 반복문 2)
        
    }
    // 반복문 1)

    return count
}

 

마무리하며

주석 없이도 무려 160줄이 넘는 코드를 작성했습니다. 코딩테스트 트라우마가 있던 제가 이 문제를 포기하지 않고 끝까지 풀어냈다는 것만도 뿌듯하긴 합니다만..

사실 주석으로 일부러 써 보기도 했지만 진짜진짜 반복문이 많았네요. 3번 중첩에 내부 반복문이 4개고 심지어 안 센 외부 반복문까지.. 필히 개선해 보면 좋을 것 같지만 지금은 너무 지쳐서 지금 당장은 말고..!

꼭꼭 다음에 개선하는 것을 목표로 두고 열심히 해야겠습니다.