[프로그래머스 / Swift] 카드 짝 맞추기

문제 접근

dfs로 문제를 풀고 싶었는데 너무 많은 호출을 하게 되어서 dfs 대신에 bfs로 접근하였다.

하지만 bfs로도 문제가 풀기는 힘들었다. 문제를 하나 하나 뜯어보자.

문제 풀이

문제를 풀기 위해서 접근해야 할 것은

1. 몇 번 카드부터 시작 할 것인가? ( 카드를 맞추는 순서는 어떻게 할 것인가? )
2. A -> B로 접근하기 위해서 가장 가까운 루트는 어떻게 구할 것인가?

이다. 하나씩 뜯어보자.

몇 번 카드부터 시작할 것인가?

1번부터 6번 카드까지 어떤 순서대로 풀어낼 것인가에 대해서는 순열을 통해서 문제를 풀어야한다.

func permutate(_ elements: [Int]) -> [[Int]] {
    var result = [[Int]]()
    
    var visited = [Bool](repeating: false, count: elements.count)
    
    func makeResult(_ arr: [Int]) {
        if arr.count == elements.count {
            result.append(arr)
            return
        }
        
        for i in 0..<visited.count {
            if !visited[i] {
                visited[i] = true
                makeResult(arr + [elements[i]])
                visited[i] = false
            }
        }
    }
    
    makeResult([])
    
    return result
}

permutate에 순열을 배합할 배열을 넣어주면

result에 순열 순서가 생긴다.

A -> B 로 접근하기 위해서 가장 가까운 루트를 어떻게 구할 것인가?

이 문제에 대한 답은 BFS이다. 

let dy = [1, -1, 0, 0]
let dx = [0, 0, 1, -1]
    
func bfs(_ from: (Int, Int), _ to: (Int, Int), _ board: [[Int]]) -> Int {
    var visited = [[Bool]](repeating: [Bool](repeating: false, count: 4), count: 4)
    var que = Queue<(Int, Int, Int)>()
    que.append((from.0, from.1, 0))
    visited[from.0][from.1] = true

    while !que.isEmpty {
        guard let (y, x, move) = que.pop() else { continue }

        if y == to.0 && x == to.1 {
            return move
        }

		// 상하좌우 움직이는 코드
        for i in 0..<4 {
            let ny = y + dy[i]
            let nx = x + dx[i]
            guard ny < 4, ny >= 0, nx < 4, nx >= 0, !visited[ny][nx] else { continue }
            que.append((ny, nx, move + 1))
            visited[ny][nx] = true
        }

		// 컨트롤 움직임 코드
        for i in 1..<4 {
            let ny = y + i
            guard ny < 4, ny >= 0 else { break }
            if board[ny][x] != 0 && visited[ny][x] {
                break
            }
            if  (board[ny][x] != 0 || ny == 3) && !visited[ny][x] {
                que.append((ny, x, move + 1))
                visited[ny][x] = true
                break
            }
        }
	
    	// 컨트롤 움직임 코드
        for i in 1..<4 {
            let ny = y - i
            guard ny < 4, ny >= 0 else { break }
            if board[ny][x] != 0 && visited[ny][x] {
                break
            }
            if (board[ny][x] != 0 || ny == 0) && !visited[ny][x] {
                que.append((ny, x, move + 1))
                visited[ny][x] = true
                break
            }
        }

		// 컨트롤 움직임 코드
        for i in 1..<4 {
            let nx = x + i
            guard nx < 4, nx >= 0 else { break }
            if board[y][nx] != 0 && visited[y][nx] {
                break
            }
            if (board[y][nx] != 0 || nx == 3) && !visited[y][nx] {
                que.append((y, nx, move + 1))
                visited[y][nx] = true
                break
            }
        }

		// 컨트롤 움직임 코드
        for i in 1..<4 {
            let nx = x - i
            guard nx < 4, nx >= 0 else { break }
            if board[y][nx] != 0 && visited[y][nx] {
                break
            }
            if (board[y][nx] != 0 || nx == 0) && !visited[y][nx] {
                que.append((y, nx, move + 1))
                visited[y][nx] = true
                break
            }
        }

    }
    return 0
}

큐는 직접 구현한 코드이다. 큐에 대한 코드는 따로 아래에 적겠다.

struct Queue<T> {
    var arr = [T]()
    var index = 0
    
    mutating func append(_ ele: T) {
        arr.append(ele)
    }
    
    mutating func pop() -> T? {
        guard !self.isEmpty else { return nil }
        
        defer {
            index += 1
        }
        
        return arr[index]
    }
    
    var isEmpty: Bool {
        index >= arr.count
    }
}

언제 어떻게 BFS를 호출할 것인가?

사실 이 문제의 키 포인트는 여기라고 생각한다. BFS를 호출하는 방식이다.

이 문제에서 BFS를 호출 할 때에 주의해야 할 점은 뒤집어야할 카드는 2개라는 것이다.

1이 적힌 A 카드 또 다른 1이 적힌 B 카드 두 개가 있다고 하자.

• 지금 위치 -> A -> B
• 지금 위치 -> B -> A

과연 어느 방식으로 가야할지 잘 모르기 때문이다.

우선 카드 별로 위치를 아는 것이 중요하다.

var cards = [Int: [(Int, Int)]]()

for y in 0..<4 {
    for x in 0..<4 where board[y][x] != 0 {
        if let _ = cards[board[y][x]] {
            cards[board[y][x]]?.append((y, x))
        } else {
            cards[board[y][x]] = [(y, x)]
        }
    }
}

4 X 4 의 작은 배열이다보니 직접 순회하면서 카드의 위치를 찾았다.

func findCard(_ y: Int, _ x: Int, _ pattern: [Int], _ board: [[Int]]) -> Int {
    if pattern.isEmpty {
        return 0
    }

    var pattern = pattern
    let num = pattern.removeLast()

    let card1 = cards[num]![0]
    let card2 = cards[num]![1]

    let first = bfs((y, x), card1, board) + bfs(card1, card2, board) + 2
    let second = bfs((y, x), card2, board) + bfs(card2, card1, board) + 2

    var board = board
    board[card1.0][card1.1] = 0
    board[card2.0][card2.1] = 0

    var result = Int.max

    result = min(result, findCard(card2.0, card2.1, pattern, board) + first)
    result = min(result, findCard(card1.0, card1.1, pattern, board) + second)

    return result == Int.max ? Int.max : result
}

var answer = Int.max
for pattern in permutate(Array(cards.keys)) {
    answer = min(answer, findCard(r, c, pattern, board))
}

그리고 find 카드 함수를 재귀호출 하면서 위치를 찾아간다.

단 모든 순열에 대해서 최소값을 비교해야한다.

왜냐하면 어떤 순서로 카드를 뒤집는 것이 가장 빠른지 모르기 때문이다.

사실 이 부분이 가장 어렵다고 생각한다. 하지만 천천히 생각하면 코드가 이해가 될 것이다.

전체 코드 보기

import Foundation

var cards = [Int: [(Int, Int)]]()


struct Queue<T> {
    var arr = [T]()
    var index = 0
    
    mutating func append(_ ele: T) {
        arr.append(ele)
    }
    
    mutating func pop() -> T? {
        guard !self.isEmpty else { return nil }
        
        defer {
            index += 1
        }
        
        return arr[index]
    }
    
    var isEmpty: Bool {
        index >= arr.count
    }
}

func permutate(_ elements: [Int]) -> [[Int]] {
    var result = [[Int]]()
    
    var visited = [Bool](repeating: false, count: elements.count)
    
    func makeResult(_ arr: [Int]) {
        if arr.count == elements.count {
            result.append(arr)
            return
        }
        
        for i in 0..<visited.count {
            if !visited[i] {
                visited[i] = true
                makeResult(arr + [elements[i]])
                visited[i] = false
            }
        }
    }
    
    makeResult([])
    
    return result
}

func solution(_ board:[[Int]], _ r:Int, _ c:Int) -> Int {
    for y in 0..<4 {
        for x in 0..<4 where board[y][x] != 0 {
            if let _ = cards[board[y][x]] {
                cards[board[y][x]]?.append((y, x))
            } else {
                cards[board[y][x]] = [(y, x)]
            }
        }
    }
    
    let dy = [1, -1, 0, 0]
    let dx = [0, 0, 1, -1]
    
    func bfs(_ from: (Int, Int), _ to: (Int, Int), _ board: [[Int]]) -> Int {
        var visited = [[Bool]](repeating: [Bool](repeating: false, count: 4), count: 4)
        var que = Queue<(Int, Int, Int)>()
        que.append((from.0, from.1, 0))
        visited[from.0][from.1] = true
        
        while !que.isEmpty {
            guard let (y, x, move) = que.pop() else { continue }

            if y == to.0 && x == to.1 {
                return move
            }
            
            
            for i in 0..<4 {
                let ny = y + dy[i]
                let nx = x + dx[i]
                guard ny < 4, ny >= 0, nx < 4, nx >= 0, !visited[ny][nx] else { continue }
                que.append((ny, nx, move + 1))
                visited[ny][nx] = true
            }
            
            for i in 1..<4 {
                let ny = y + i
                guard ny < 4, ny >= 0 else { break }
                if board[ny][x] != 0 && visited[ny][x] {
                    break
                }
                if  (board[ny][x] != 0 || ny == 3) && !visited[ny][x] {
                    que.append((ny, x, move + 1))
                    visited[ny][x] = true
                    break
                }
            }
            
            for i in 1..<4 {
                let ny = y - i
                guard ny < 4, ny >= 0 else { break }
                if board[ny][x] != 0 && visited[ny][x] {
                    break
                }
                if (board[ny][x] != 0 || ny == 0) && !visited[ny][x] {
                    que.append((ny, x, move + 1))
                    visited[ny][x] = true
                    break
                }
            }
            
            for i in 1..<4 {
                let nx = x + i
                guard nx < 4, nx >= 0 else { break }
                if board[y][nx] != 0 && visited[y][nx] {
                    break
                }
                if (board[y][nx] != 0 || nx == 3) && !visited[y][nx] {
                    que.append((y, nx, move + 1))
                    visited[y][nx] = true
                    break
                }
            }
            
            for i in 1..<4 {
                let nx = x - i
                guard nx < 4, nx >= 0 else { break }
                if board[y][nx] != 0 && visited[y][nx] {
                    break
                }
                if (board[y][nx] != 0 || nx == 0) && !visited[y][nx] {
                    que.append((y, nx, move + 1))
                    visited[y][nx] = true
                    break
                }
            }
            
        }
        return 0
    }

    func findCard(_ y: Int, _ x: Int, _ pattern: [Int], _ board: [[Int]]) -> Int {
        if pattern.isEmpty {
            return 0
        }
        
        var pattern = pattern
        let num = pattern.removeLast()
        
        let card1 = cards[num]![0]
        let card2 = cards[num]![1]
        
        let first = bfs((y, x), card1, board) + bfs(card1, card2, board) + 2
        let second = bfs((y, x), card2, board) + bfs(card2, card1, board) + 2
        
        var board = board
        board[card1.0][card1.1] = 0
        board[card2.0][card2.1] = 0
        
        var result = Int.max
        
        result = min(result, findCard(card2.0, card2.1, pattern, board) + first)
        result = min(result, findCard(card1.0, card1.1, pattern, board) + second)
        
        return result == Int.max ? Int.max : result
    }

    var answer = Int.max
    for pattern in permutate(Array(cards.keys)) {
        answer = min(answer, findCard(r, c, pattern, board))
    }
    
    return answer
}

문제 후기

음 BFS 순열 그리고 문제해결 까지 3박자가 어울려저서 꽤 어려운 문제라고 생각한다.

Lv 3은 아닌것 같다. Lv 4 난이도를 가진 문제라고 생각한다.

[문제 링크]