[프로그래머스] Swift - 퍼즐 조각 채우기

https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

 

2024.01.12 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• game_board와 table이라는 2차원 배열 제공
• 게임 보드에는 빈 칸들이 있고 table에는 이 빈칸에 들어갈 퍼즐들이 있다.
• 빈칸과 퍼즐들은 1x1 크기의 칸들로 연결될 수 있으며 한 뭉치는 상하좌우로만 연결되어 있다. (대각선에 있는 것은 연결로 취급 X)
• 퍼즐들로 빈칸을 채우려고 할 때 총 몇칸을 채울 수 있는지 최댓값을 구하자
• 이 때 빈칸에 정확히 퍼즐이 들어 맞아야 해당 퍼즐을 빈칸에 넣을 수 있다.
• 퍼즐은 회전이 가능하고 뒤집는 것은 불가능하다.

 

다음과 같은 순서로 문제를 하나씩 해결했습니다.

 

1. table에서 도형(퍼즐) 찾기 (해당 퍼즐을 구성하는 모든 좌표를 묶어서 저장)

2. game_board에서 빈칸 찾기 (마찬가지로 모든 좌표를 묶어서 저장)

3. 2번에서 찾은 빈칸 배열을 순회하며 들어 맞는 퍼즐이 있는지 확인 (퍼즐을 회전시켜서 확인해야 함)

4. 맞는 퍼즐이 있다면 result를 해당 빈칸 덩어리의 칸 수 만큼 증가시키고 퍼즐 배열에서 사용한 퍼즐 제거

 

 

1번 작업은 BFS를 활용했습니다.

상하좌우로 탐색을 이어가며 퍼즐을 찾고 퍼즐을 구성하는 좌표들을 배열에 저장합니다.

이 때 퍼즐의 좌표들을 좌상단으로 옮긴 형태로 저장합니다.

즉, (0, 0)에 최대한 가깝게 옮겨서 저장하는 것입니다.

이렇게 옮기는 이유는 이후에 빈칸의 좌표들과 비교할 때 같은 위치로 이동시켜놓아야 퍼즐이 빈칸에 들어갈 수 있는지 파악할 수 있기 때문입니다.

 

2번 작업도 마찬가지로 BFS를 활용했습니다.

빈칸 역시 (0, 0) 방향으로 옮겨서 저장합니다.

 

여기까지 하면 사전 작업은 모두 끝났습니다.

 

빈칸 배열과 퍼즐 배열을 2중 for문으로 순회하며 해당 빈칸을 채울 수 있는 퍼즐을 찾습니다.

90도씩 4번 회전하여 이 퍼즐이 빈칸에 들어갈 수 있는지 체크하면 됩니다.

 

회전은 약간의 수학적인 개념이 필요합니다.

오른쪽으로 90도 회전시킨다면 (x, y)좌표가 (y, 배열의row수-1-x)가 됩니다.

 

회전 시킨 퍼즐이 빈칸에 들어간다면 result를 증가시키고 퍼즐 배열에서 사용한 퍼즐을 제거하여 중복해서 계산하는 것을 방지합니다.

 

 

 

풀이

1. 좌표 정보를 담을 구조체 생성

fileprivate struct Coord: Equatable { 
    let x: Int
    let y: Int
}

2. 퍼즐 찾기 bfs 함수 구현 및 실행

함수들은 solution 함수의 내부에 구현했습니다.

    // 도형 찾기 (bfs)
    var visited = Array(repeating: Array(repeating: false, count: table[0].count), count: table.count)
    var figures = [[Coord]]() // 각 도형들은 좌상단으로 옮겨서 저장
    
    let dx = [0, 0, 1, -1]
    let dy = [1, -1, 0, 0]
    
    func bfs(x: Int, y: Int) {
        var result = [(Int, Int)]()
        var queue = [(Int, Int)]()
        
        queue.append((x, y))
        
        while !queue.isEmpty {
            let now = queue.removeFirst()
            result.append(now)
            
            for i in 0..<4 {
                let nextX = now.0 + dx[i]
                let nextY = now.1 + dy[i]
                
                if nextX >= 0 && nextX < table.count && nextY >= 0 && nextY < table[0].count {
                    if visited[nextX][nextY] == false && table[nextX][nextY] == 1 {
                        visited[nextX][nextY] = true
                        queue.append((nextX, nextY))
                    }
                }
            }
        }
        
        let minX = result.sorted(by: { $0.0 < $1.0 })[0].0
        let minY = result.sorted(by: { $0.1 < $1.1 })[0].1
        
        figures.append(result.map { Coord(x: $0.0-minX, y: $0.1-minY) })
    }
    
    for x in table.indices {
        for y in table[0].indices {
            if visited[x][y] == false && table[x][y] == 1 {
                visited[x][y] = true
                bfs(x: x, y: y)
            }
        }
    }

 

minX,  minY는 좌표를 좌상단으로 이동시키기 위해 필요한 값입니다.

 

3. 빈칸 찾기 bfs 함수 구현 및 실행

var boardVisited = Array(repeating: Array(repeating: false, count: game_board[0].count), count: game_board.count)
    var blanks = [[Coord]]()
    
    func findBlank(x: Int, y: Int) {
        var result = [(Int, Int)]()
        var queue = [(Int, Int)]()
        
        queue.append((x, y))
        
        while !queue.isEmpty {
            let now = queue.removeFirst()
            result.append(now)
            
            for i in 0..<4 {
                let nextX = now.0 + dx[i]
                let nextY = now.1 + dy[i]
                
                if nextX >= 0 && nextX < game_board.count && nextY >= 0 && nextY < game_board[0].count {
                    if boardVisited[nextX][nextY] == false && game_board[nextX][nextY] == 0 {
                        boardVisited[nextX][nextY] = true
                        queue.append((nextX, nextY))
                    }
                }
            }
        }
        
        let minX = result.sorted(by: { $0.0 < $1.0 })[0].0
        let minY = result.sorted(by: { $0.1 < $1.1 })[0].1
        
        blanks.append(result.map { Coord(x: $0.0-minX, y: $0.1-minY) })
    }
    
    for x in game_board.indices {
        for y in game_board[0].indices {
            if boardVisited[x][y] == false && game_board[x][y] == 0 {
                boardVisited[x][y] = true
                findBlank(x: x, y: y)
            }
        }
    }

 

여기까지 하면 figures 배열에는 퍼즐들이 blanks 배열에는 빈칸들이 들어있게 됩니다.

 

 

4. 회전 함수 구현

fileprivate func rotate(arr: [Coord]) -> [Coord] {
    let maxX = arr.max(by: { $0.x < $1.x })!.x
    
    return arr.map { Coord(x: $0.y, y: maxX-$0.x) }
}

 

앞서 말한 수학적 원리로 90도 회전한 위치를 구합니다.

 

5. 빈칸에 들어갈 퍼즐 찾기

    var result = 0
    outer: for blank in blanks {
        for (index, figure) in figures.enumerated() {
            if figure.count != blank.count { continue }
            var prev = figure
            for _ in 0..<4 {
                // 회전시키며 검사
                let rotated = rotate(arr: prev)
                prev = rotated
                if rotated.sorted(by: { ($0.x, $0.y) < ($1.x, $1.y) }) == blank.sorted(by: { ($0.x, $0.y) < ($1.x, $1.y) }) {
                    figures.remove(at: index)
                    result += blank.count
                    continue outer
                }
            }
        }
    }

 

퍼즐을 90도씩 4회 회전시키며 빈칸에 들어갈지 확인합니다.

그전에 figure.count != blank.count 이면 빈칸을 구성하는 칸의 개수와 퍼즐을 구성하는 칸의 개수가 다르기 때문에 아무리 회전해도 넣을 수 없습니다. 따라서 바로 continue 시킵니다.

 

 

이제 result를 리턴하면 solution 함수가 완료됩니다.

 

 

 

마무리

우선 BFS에 대한 확실한 이해가 필요했습니다.

2번의 BFS를 각각 수행해야 했고 도형의 비교를 위해 구한 좌표들을 (0,0) 방향으로 최대한 이동시키는 아이디어도 필요했습니다.

 

또한 배열의 회전이라는 수학적인 구현도 필요했습니다.

 

다행히 보드의 크기가 최대 50으로 제한되어 시간 복잡도는 크게 신경쓰지 않아도 됐습니다.

 

회전 문제의 경우 저는 종이에 직접 그려서 회전 규칙을 찾기도 합니다. (이번 문제도 사실 여러번 그려보고 이해했습니다.. ㅎㅎ)