코딩테스트 연습 - 퍼즐 조각 채우기

문제 풀이 아이디어

많이 어려운 문제입니다… 저도 거의 1시간 30분 이상 걸린 것 같네요. (그 중에 한 사용한 블록 체크 위치를 잘못해서 1시간 잡아먹음…) 아래 3단계에 걸쳐서 문제를 풀어보겠습니다.

1. 퍼즐 찾기

일단 퍼즐 조각을 찾아야 합니다. 퍼즐 조각을 찾는 것이야 그냥 dfs를 사용하면 쉽게할 수 있으니 문제가 되지 않습니다만 문제는 퍼즐 조각을 저장하는 것입니다. 퍼즐조각을 그냥 이차원 배열 상의 위치로 저장하게 되면 나중에 퍼즐을 맞추는 과정에서 문제가 발생합니다. 그 퍼즐 조각이 game_board의 정확히 동일한 위치에 있지 않기 때문입니다.

따라서 퍼즐조각을 저장할 때는 위치와 모양이 아니라 모양만 저장해야 합니다. 저장할 때 아래와 같이 이중반복문을 통해 dfs가 시작되는 점을 (0, 0)으로 하여 다른 칸들의 상대적 위치만 저장합니다.

5번 조각을 예로 들어볼까요? 해당 퍼즐에서 dfs가 시작되는 점은 5라는 숫자가 적힌 조각입니다. 해당 칸을 (0, 0)으로 저장합니다. 그리고 다음 칸은 (0, 0)를 기준으로 1행 아래에 있으므로 (0, 1)이 됩니다. 따라서 5번 퍼즐은 [(0, 0), (1, 0)]로 저장합니다. 이렇게 하면 테이블 위에서의 위치와는 독립적으로 퍼즐 조각의 모양만 저장할 수 있습니다.

2. 퍼즐 돌리기

이제 퍼즐을 돌려야 합니다. 저는 퍼즐이 놓여있는 테이블 자체를 돌린 다음에 다시 퍼즐을 구하는 방법 사용했습니다. 기존의 퍼즐과 새로 구하는 퍼즐을 매칭시키기 위해서 최초에 퍼즐을 구하는 dfs를 할 때 퍼즐을 종류 별로 숫자로 표시합니다. 이렇게 하면 퍼즐 자체, 예를 들면 위에서 구한 5번 퍼즐인 [(0, 0), (1, 0)],를 돌리는 방법 보다 훨씬 직관적으로 돌린 퍼즐의 형태를 구할 수 있습니다. 그리고 dfs가 시작하는 점인 (0, 0)을 기준으로 회전하는 모양이 그대로 저장할 수 있기 때문에 game_board에서 dfs로 찾은 구멍의 모양과 그대로 비교할 수 있다는 점도 장점입니다.

물론 코드가 엄청 길어진다는 단점도 있습니다. 구글링을 해서 찾은 코드들이랑 비교해 봤을 때 제 코드가 압도적으로 길더군요. 다음에 다시 풀어볼 때는 퍼즐 자체를 돌리는 방법도 연구해봐야겠습니다.

3. 빈 공간 찾아서 퍼즐 넣기

이제 game_board로 이동해서 퍼즐을 찾을 때와 동일한 dfs를 통해서 퍼즐과 일치하는 빈 공간을 찾습니다. 일단 빈공간을 만날 때 마다 dfs를 실시해서 퍼즐과 동일하게 모양만 저장합니다.

그 모양을 모든 퍼즐조각과 비교해서 일치하는 조각이 있으면 퍼즐을 맞추어 넣으면 됩니다.

물론 퍼즐은 한번만 사용할 수 있으므로 사용한 퍼즐은 체크해두는 것을 잊지 맙시다!

나머지는 코드로 설명드리겠습니다. 말로만 설명하기는 힘듭니다. 물론 코드를 봐도 이해하기 힘드실거에요. 제가 구글링 열심히 해서 많은 코드를 참고 했는데 이해가 잘 안되어서 제 코드에 적용해보려고 해도 잘 안되더라구요ㅠㅠ 결국 아래 코드는 제가 최초에 푼 코드에 주석만 첨부한 것입니다. 위에 아이디어만 참고하시고 직접 풀어보시는 것을 추천합니다!

코드

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
    let dr = [1, -1, 0, 0]
    let dc = [0, 0, 1, -1]
    
    var table = table
    
    // 퍼즐이 놓인 테이블을 회전하는 함수
    func rotateTable() {
        let length = table.count
        var newTable = Array(repeating: Array(repeating: 0, count: length), count: length)
        
        for r in 0..<length {
            for c in 0..<length {
                newTable[r][c] = table[c][length - r - 1]
            }
        }
        
        table = newTable
    }
    
    // 유효한 좌표인지 리턴하는 함수
    func isValid(_ r: Int, _ c: Int) -> Bool {
        r >= 0 && r < table.count && c >= 0 && c < table.count
    }
    
    // 최초의 퍼즐조각 (테이블을 회전하기 전)을 찾는 함수
        // 퍼즐조각을 찾을 때마다 해당 퍼즐조각이 놓인 칸에 번호를 매긴다.
    func findFirstPuzzles() {
        var cnt = 1
        var visited1 = Array(repeating: Array(repeating: false, count: table.count), count: table.count)
        
        
        func dfs(_ r: Int, _ c: Int) {
            let origin = (r, c)
            // dfs를 위한 stack에 넣기 및 방문체크
            var stack = [(Int, Int)]()
            stack.append(origin)
            visited1[r][c] = true
            
            // 테이블에 블록 번호 쓰기
            table[r][c] = cnt
            
            // 블록 배열 만들기 (원점을 (0, 0) 기준으로)
            var block = [(Int, Int)]()
            block.append((0, 0))
            
            while !stack.isEmpty {
                let now = stack.popLast()!
                table[now.0][now.1] = cnt
                for i in 0..<4 {
                    let nr = now.0 + dr[i], nc = now.1 + dc[i]
                    if isValid(nr, nc) && table[nr][nc] != 0 && !visited1[nr][nc] {
                        stack.append((nr, nc))
                        visited1[nr][nc] = true
                        // 블록 번호 쓰기
                        table[nr][nc] = 1
                        // 블록에 원점 기준으로 다른 조각의 위치 넣기
                        block.append((nr - origin.0, nc - origin.1))
                    }
                }
            }
            
            // dfs가 끝나면 블록들에 넣고
            puzzles.append([block])
            // 블럭 번호 추가
            cnt += 1
        }
        
        for r in 0..<table.count {
            for c in 0..<table.count {
                if table[r][c] != 0 && !visited1[r][c] {
                    dfs(r, c)
                }
            }
        }
    }
    
    // 회전한 테이블에서 퍼즐을 찾는 함수
        // dfs를 통해서 퍼즐을 찾는데 퍼즐의 번호가 table에 저장되어 있으므로
        // 해당 번호를 통해서 puzzles[번호]에 해당 퍼즐을 저장한다.
    func findRotatedPuzzles() {
        var visited2 = Array(repeating: Array(repeating: false, count: table.count), count: table.count)

        func dfs(_ r: Int, _ c: Int) {
            let blockNumber = table[r][c]
            let origin = (r, c)

            var stack = [(Int, Int)]()
            stack.append(origin)
            visited2[r][c] = true

            var block = [(Int, Int)]()
            block.append((0, 0))

            while !stack.isEmpty {
                let now = stack.popLast()!
                for i in 0..<4 {
                    let nr = now.0 + dr[i], nc = now.1 + dc[i]
                    if isValid(nr, nc) && table[nr][nc] != 0 && !visited2[nr][nc] {
                        stack.append((nr, nc))
                        visited2[nr][nc] = true
                        block.append((nr - origin.0, nc - origin.1))
                    }
                }
            }
            puzzles[blockNumber].append(block)
        }

        for r in 0..<table.count {
            for c in 0..<table.count {
                if table[r][c] != 0 && !visited2[r][c] {
                    dfs(r, c)
                }
            }
        }
    }
    
    // 모든 퍼즐을 찾는 함수
        // 최초에 1회 + 90도, 180도, 270도 회전 총 3회
    func findAllPuzzles() {
        findFirstPuzzles()
        
        for _ in 0..<3 {
            rotateTable()
            findRotatedPuzzles()
        }
    }
    
    // 퍼즐을 넣을 구멍의 모양을 리턴하는 함수
        // 퍼즐과 동일하게 (0, 0)을 기준으로 모양만 저장
    func findSpace(_ r: Int, _ c: Int) -> [(Int, Int)] {
        let origin = (r, c)
        var hole = [(0, 0)]
        var stack = [origin]
        visited[r][c] = true
        
        while !stack.isEmpty {
            let now = stack.popLast()!
            for i in 0..<4 {
                let nr = now.0 + dr[i]
                let nc = now.1 + dc[i]
                if isValid(nr, nc) && game_board[nr][nc] == 0 && !visited[nr][nc] {
                    hole.append((nr - origin.0, nc - origin.1))
                    stack.append((nr, nc))
                    visited[nr][nc] = true
                }
            }
        }
        
        return hole
    }
    
    // 일치하는 퍼즐 조각을 찾는 함수
    func findMatchingPuzzle(_ space: [(Int, Int)]) -> Int {
        
        // 두 [(Int, Int)] 자료형이 동일한지 판정하는 함수
            // (Int, Int)가 Equatable이 아니기 때문에 구현
        func isMatching(_ space: [(Int, Int)], _ block: [(Int, Int)]) -> Bool {
            guard space.count == block.count else { return false }
            for i in 0..<space.count {
                if space[i].0 != block[i].0 || space[i].1 != block[i].1 {
                    return false
                }
            }
            return true
        }
        
        // 모든 퍼즐을 탐색하면서 일치하는 퍼즐을 찾는다.
        for i in 1..<puzzles.count {
            // 해당 퍼즐이 이미 쓰인 퍼즐이라면 continue
            guard usedPuzzle[i] == false else { continue }
            for j in 0..<4 {
                if isMatching(space, puzzles[i][j]) { return i }
                // 똑같은 퍼즐이 있다면 해당 퍼즐의 번호를 리턴
            }
        }
        
        // 똑같은 모양의 퍼즐이 없다면 0을 리턴
        return 0
    }
    
    var puzzles: [[[(Int, Int)]]] = [[]]
    
    findAllPuzzles()
    
    var visited = Array(repeating: Array(repeating: false, count: game_board.count), count: game_board.count)
    var usedPuzzle = Array(repeating: false, count: puzzles.count)
    var answer = 0
    
    for r in 0..<game_board.count {
        for c in 0..<game_board.count {
            // game_board에 방문하지 않은 빈 공간이 발견되면
            if game_board[r][c] == 0 && !visited[r][c] {
                // dfs해서 빈공간을 찾고
                let space = findSpace(r, c)
                // 칸은 모양의 퍼즐을 찾는다.
                let matchingPuzzle = findMatchingPuzzle(space)
                // 똑같은 모양의 퍼즐이 없다면 (리턴값 0) 다른 공간을 찾는다.
                if matchingPuzzle == 0 {
                    continue
                // 똑같은 모양의 퍼즐이 있다면 해당 퍼즐을 사용체크하고 space의 크기를 답에 더한다.
                } else {
                    usedPuzzle[matchingPuzzle] = true
                    answer += space.count
                }
            }
        }
    }
    
    return answer
}

문법 Tip! : 해당 범위에 포함하는지 확인하는 연산자

제가 여지껏 이차원 배열의 isValid를 만들 때는 아래와 같이 만들었는데요.

func isValid(_ r: Int, _ c: Int) -> Bool {
    r >= 0 && r < table.count && c >= 0 && c < table.count
}

다른 분의 풀이 중에 좀 더 간단한 syntactic sugar가 있어서 활용해 보았습니다 ~= 연산자인데요. 왼쪽에 Range, 오른쪽에 Int를 두면 Int가 Range 안에 포함되는지를 Bool로 반환하는 연산자입니다.

func isValid(_ r: Int, _ c: Int) -> Bool {
    0..<table.count ~= r && 0..<table.count ~= c
}