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

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

카카오 2021 블라인드 채용

4*4인 판에 최대 6종류의 카드쌍(1종류당 2장)이 뒤집혀있다

한번에 두장의 카드를 뒤집어서 같은 종류의 카드면 카드를 지울 수 있고

다른 종류의 카드면 카드를 다시 뒤집어야한다.

 

이때 모든 이동 횟수와 카드를 뒤집는 횟수는 누적되며 이를 조작횟수라고 하면, 최소 조작 횟수를 반환하는 문제이다.

이 게임에서의 이동은 방향키로 상하좌우 1칸씩 이동하는 것과 ctrl+방향키로 해당 방향의 카드가 있는 곳으로 한번에 이동하거나 해당 방향에 카드가 없다면 끝자리로 이동하는 것이 가능하다.

 

접근방법

처음에는 dfs로 풀려고 했는데 무한반복되는 경우가 있어서 다른 블로그를 참고하여 bfs로 풀었다.

카드 종류별로 어디를 먼저 방문할지를 정한 뒤에 최소 경로를 bfs로 찾아서 풀이하지 않고

4*4로 크기가 작은 만큼 방향키, ctrl+방향키, 뒤집기를 갈 수 있는 모든 경우로 취급하고

현재의 상태를 담은 board를 함께 q에 넣으면서 bfs로 풀었다.

 

즉, 시작위치만 주어지면 거기서 할 수 있는 모든 조작의 모든 경우를 bfs로 다 구한다는 말이 된다.

bfs이기 때문에 bfs반복문을 돌면서 모든 카드를 뒤집게 되면 그때까지 누적된 조작 횟수를 리턴하면

그 값이 최소 조작 횟수가 된다. (너비 우선 탐색이니까)

 

프로그래머스 - 카드 짝 맞추기 (2021 카카오 블라인드 공채)

프로그래머스 - 카드 짝 맞추기 (2021 카카오 블라인드 공채)

로직은 이 블로그와 거의 똑같다

 

소스코드

import Foundation

let dir:[[Int]] = [[0,1], [0,-1], [1,0], [-1,0]]
var visit:Set<Status> = []

struct Card:Hashable {
    let r:Int
    let c:Int
    let num:Int
}

struct Status:Hashable{
    let board:[[Int]]
    let r:Int
    let c:Int
    let openCard:Card?
    
    init (_ board:[[Int]], _ r:Int, _ c:Int, _ openCard:Card?) {
        self.board = board
        self.r = r
        self.c = c
        self.openCard = openCard
    }
}

func isAllCardOpened(_ cBoard:[[Int]]) -> Bool {
    for card in Array(cBoard.flatMap{$0}) {
        if card != 0 {
            return false
        }
    }
    
    return true
}

func isOnEnd(_ r:Int, _ c:Int, _ dir:Int) -> Bool {
    if (dir == 0 && c == 3) ||
    (dir == 1 && c == 0) ||
    (dir == 2 && r == 3) ||
    (dir == 3 && r == 0) {
        return true
    } else {
        return false
    }
}

func solution(_ board:[[Int]], _ r:Int, _ c:Int) -> Int {
    var queue:[(status:Status, moveCnt:Int)] = []
    
    queue.append((Status(board,r,c,nil),0))
    visit.insert(Status(board,r,c,nil))
        
    while !queue.isEmpty {
        let q = queue.removeFirst()
        
        var cBoard:[[Int]] = q.status.board
        let cr:Int = q.status.r
        let cc:Int = q.status.c
        let openCard:Card? = q.status.openCard
        let moveCnt:Int = q.moveCnt

        // 방향키
        for d in dir {
            let nr:Int = cr + d[0]
            let nc:Int = cc + d[1]
            if nr < 0 || nr > 3 || nc < 0 || nc > 3 {
                continue
            } else if visit.contains(Status(cBoard,nr,nc,openCard)) {
                continue
            } else {
                queue.append((Status(cBoard,nr,nc,openCard), moveCnt+1))
                visit.insert(Status(cBoard,nr,nc,openCard))
            }
        }

        // ctrl + 방향키
        for (i,d) in dir.enumerated() {
            
            var nr:Int = cr + d[0]
            var nc:Int = cc + d[1]
            
            if nr < 0 || nr > 3 || nc < 0 || nc > 3 {
                continue
            }
            
            while cBoard[nr][nc] == 0 && !isOnEnd(nr,nc,i) {
                nr = nr + d[0]
                nc = nc + d[1]
            }
            
            if visit.contains(Status(cBoard,nr,nc,openCard)) {
                continue
            } else {
                queue.append((Status(cBoard,nr,nc,openCard), moveCnt+1))
                visit.insert(Status(cBoard,nr,nc,openCard))
            }
        }
        
        // open
        // 짝을 맞출 카드가 있을 경우
        if let openedCard = openCard {
            // 짝 맞음
            if openedCard.num == cBoard[cr][cc] && !(openedCard.r == cr && openedCard.c == cc) {
                cBoard[openedCard.r][openedCard.c] = 0
                cBoard[cr][cc] = 0
                
                if isAllCardOpened(cBoard) {
                    return moveCnt+1
                }
                
                visit.insert(Status(cBoard,cr,cc,nil))
                queue.append((Status(cBoard,cr,cc,nil),moveCnt+1))
            }
            // 짝 틀림
            else {
                if visit.contains(Status(cBoard,cr,cc,openCard)) {
                    continue
                } else {
                    queue.append((Status(cBoard,cr,cc,nil), moveCnt+1))
                    visit.insert(Status(cBoard,cr,cc,nil))
                }
            }
        }
        // 새로 카드를 오픈할 때
        else {
            let newOpenCard = Card(r:cr, c:cc, num:cBoard[cr][cc])
            
            if visit.contains(Status(cBoard,cr,cc,newOpenCard)) {
                continue
            }
            queue.append((Status(cBoard,cr,cc,newOpenCard), moveCnt+1))
            visit.insert(Status(cBoard,cr,cc,newOpenCard))
        }
    }
    return Int.max
}