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

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

프로그래머스

 

2023.11.14 기준 Level 3

 

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

 

아이디어

문제 조건

• 4x4 사이즈의 격자(2차원 배열) 존재
• 배열의 각 원소는 0~6까지의 수
  • 0은 빈 칸
  • 1~6은 카드 번호
• 각 카드 번호는 2개씩 중복하여 배열에 있다.
• 뒷면이 보이도록 뒤집혀 있는 상태에서 시작한다.
• 한 카드씩 앞면이 보이도록 뒤집을 수 있는데 2개의 카드를 뒤집었을 때 두 카드가 같은 번호라면 배열에서 제거한다.
• 두 카드가 다른 카드 번호라면 다시 뒷면이 보이도록 뒤집어둔다.
• 커서는 상하좌우로 한칸씩 이동하는 방식과 빈칸을 건너뛰고 카드가 나올 때까지 상하좌우로 움직이는 방식이 있으며 두 방식 모두 1회로 카운팅한다.
• 모든 카드를 제거할 때 필요한 최소 조작 횟수를 구해야 한다.

 

문제에서 이미 배열의 카드 번호를 다 알려주고 있기 때문에 다시 뒷면이 보이도록 뒤집는 작업은 배제할 수 있습니다.

 

이 문제는 복잡해보이지만 잘 추상화해서 생각을 해보면 복잡하지 않습니다.

 

1. 카드를 하나 앞면이 보이도록 뒤집은 상태 (enter를 한 상태)
2. 뒤집은 카드가 없는 상태

크게 두 가지 상태로 구분할 수 있습니다.

 

첫 번째 상태에서는

1. 해당 카드의 짝을 찾아 이동한다.
2. 특정 카드로의 최단 거리를 구해야 하기 때문에 bfs를 사용하여 필요한 조작 횟수를 구한다.

두 번째 상태에서는

1. 뒤집혀 있는 카드가 없기 때문에 우선 카드 하나를 정해서 뒤집어야 한다.
2. 이를 위해 남아 있는 카드들을 전부 구하고 반복문을 돌며 하나씩 뒤집는 경우를 추가한다.

 

이렇게 각 상태에 따라 행동을 구분할 수 있습니다.

 

어쨌든 모든 경우의 수를 탐색해서 최소 비용을 구해야 하기 때문에 탐색 알고리즘을 사용해야 합니다. dfs, bfs 다 가능하겠지만 저는 dfs를 사용했습니다.

 

func dfs(now: [[Int]], x: Int, y: Int, cnt: Int, entered: Int)

 

dfs 선언부입니다.

 

현재 상태의 격자를 now로 받습니다.

x, y는 현재 커서 위치입니다.

cnt는 현재까지의 조작 횟수입니다.

entered는 뒤집혀 있는 카드 번호입니다. (뒤집은 카드가 없다면 0을 넣게 됩니다.)

 

앞서 각 상태에 따라 처리할 동작들을 분리했기 때문에 해당 로직을 이 dfs 함수에 넣으면 됩니다.

 

추가적으로 필요한 로직은 현재 커서 위치에서 특정 카드로의 최단 거리(최소 조작 횟수)를 구하는 로직입니다.

이 로직은 bfs를 사용하여 구현했습니다.

// 특정 위치까지의 최단 경로 찾기, 걸린 횟수와 위치 리턴
fileprivate func bfs(board: [[Int]], x: Int, y: Int, target: Int) -> (x: Int, y: Int, cnt: Int)

 

board와 현재 위치를 받고

target에 목표 지점의 카드 번호를 받습니다.

bfs의 리턴 값은 목표 카드 번호의 위치와 해당 위치까지 이동하는데 필요한 조작 횟수를 튜플로 리턴합니다.

 

이 bfs 함수 안에 방향키 이동과 Ctrl+방향키 조작의 경우를 구현하면 되는 것입니다.

 

이렇게 하면 dfs 함수에서는 방향키와 관련된 문제 조건에 대해 몰라도 되고 커서 이동 로직은 온전히 bfs 함수에서 담당하기 때문에 일종의 캡슐화가 되어 문제를 해결하기 간편해집니다.

 

그리고 enter 또한 조작 횟수에 카운팅을 해야 하는데 이건 마지막에 한번에 더해줄 수 있습니다.

왜냐하면 enter는 결국 초기 카드 개수 만큼만 필요하기 때문입니다.

즉, 커서 이동 로직에 enter는 배제하고 구현합니다.

 

 

풀이

1. 좌표의 인덱스 범위 확인 함수 구현

fileprivate func isInBoardSize(x: Int, y: Int) -> Bool {
    return x >= 0 && x < 4 && y >= 0 && y < 4
}

 

본격적인 풀이 함수 구현에 앞서 특정 위치가 4x4 사이즈 격자 안에 있는지 확인하는 함수를 만들었습니다.

true를 리턴하면 해당 격자(2차원 배열) 인덱스 안에 있기 때문에 board[x][y] 처럼 접근해도 안전합니다.

 

2. bfs 함수 구현

// 특정 위치까지의 최단 경로 찾기, 걸린 횟수와 위치 리턴
fileprivate func bfs(board: [[Int]], x: Int, y: Int, target: Int) -> (x: Int, y: Int, cnt: Int) {
    var q = [(x: Int, y: Int, cnt: Int)]()
    var visited = Array(repeating: Array(repeating: false, count: 4), count: 4)
    
    q.append((x, y, 0))
    visited[x][y] = true
    
    let dx = [0, 0, 1, -1]
    let dy = [1, -1, 0, 0]
    
    while !q.isEmpty {
        let now = q.removeFirst()
        let curX = now.x
        let curY = now.y

        if board[curX][curY] == target {
            return now
        }
        
        // 4 방향
        for i in 0..<4 {
            let nx = curX + dx[i]
            let ny = curY + dy[i]
            
            if isInBoardSize(x: nx, y: ny) {
                if visited[nx][ny] == false {
                    q.append((nx, ny, now.cnt+1))
                    visited[nx][ny] = true
                }
            }
        }
        
        // ctrl
        for i in 0..<4 {
            var tempX = curX
            var tempY = curY
            
            while isInBoardSize(x: tempX+dx[i], y: tempY+dy[i]) {
                tempX += dx[i]
                tempY += dy[i]
                
                if board[tempX][tempY] != 0 {
                    break
                }
            }
            
            if visited[tempX][tempY] == false {
                q.append((tempX, tempY, now.cnt+1))
                visited[tempX][tempY] = true
            }
        }
    }
    
    return (0,0,0)
}

 

이번 문제의 핵심 부분입니다.

현재 위치 (x, y)로 부터 짝 카드 (target)까지 필요한 조작 횟수를 구하고 target 의 위치를 리턴하는 함수입니다.

 

다른 말로 커서 이동 로직에 해당됩니다.

 

1. 우선 큐를 생성합니다. (변수 q)
2. 같은 노드 재방문을 막기 위해 visited 배열에 방문 여부를 기록합니다.
3. 현재 위치를 큐에 넣습니다.
4. while문을 돌며 bfs를 수행합니다.
   1. dequeue하기
   2. 상하좌우 방향키 이동 경우의 수를 q에 넣기
   3. Cntrl+방향키 이동 경우의 수를 q에 넣기
      1. cntrl+ 방향키는 빈 칸이 있는 경우 쭉 이동하기 때문에 while문으로 카드를 만나거나 격자의 테두리를 만날 때까지 계속 이동시킵니다.
5. target 카드를 만나면 리턴합니다.

 

3. dfs 함수 구현

fileprivate func solution(_ board:[[Int]], _ r:Int, _ c:Int) -> Int {
    
    var result = Int.max
    var enterCnt = 0
    
    for row in board {
        for item in row {
            if item != 0 {
                enterCnt += 1
            }
        }
    }
    
    func dfs(now: [[Int]], x: Int, y: Int, cnt: Int, entered: Int) {
        // base case: 전부 0이 된 상태 (모든 카드 확인 완료)
        if now.allSatisfy({ $0.reduce(0, +) == 0 }) {
            result = min(result, cnt)
            return
        }
        
        // entered가 있다면 곧바로 해당 카드를 찾아가기
        if entered != 0 {
            let res = bfs(board: now, x: x, y: y, target: entered)
            var temp = now
            temp[res.x][res.y] = 0
            dfs(now: temp, x: res.x, y: res.y, cnt: cnt + res.cnt, entered: 0)
        } else {
            // entered가 없다면 남아 있는 카드를 구하고 반복문을 돌며 해당 카드로 이동
            var cards = Set<Int>()
            for row in now {
                for item in row {
                    if item != 0 {
                        cards.insert(item)
                    }
                }
            }
            
            for card in cards {
                let res = bfs(board: now, x: x, y: y, target: card)
                var temp = now
                temp[res.x][res.y] = 0
                dfs(now: temp, x: res.x, y: res.y, cnt: cnt + res.cnt, entered: card)
            }
        }
    }
    
    dfs(now: board, x: r, y: c, cnt: 0, entered: 0)
    
    // 엔터 횟수는 최초부터 정해져 있음 (카드의 수)
    return result + enterCnt
}

 

1. enter 횟수를 구하기 위해 초기 상태에서 카드 개수를 구하여 저장합니다. (enterCnt)
2. dfs 함수를 구현합니다.
   1. now의 원소가 모두 0이면 종료된 상황이기 때문에 result를 업데이트하고 리턴합니다.
   2. entered가 0이 아니라면 짝을 찾아야 하는 상황입니다.
      1. bfs를 호출하여 짝의 위치를 찾고 reuslt에 조작 횟수를 더합니다.
      2. 찾은 짝을 제거합니다. (0으로 바꿈)
      3. dfs를 재귀적으로 호출합니다.
   3. enter가 0이라면 아무것도 뒤집지 않은 상태이기 때문에 카드 하나를 뒤집어야 합니다.
      1. 반복문을 돌아서 격자에 남아 있는 카드 종류를 찾습니다. (찾아서 set에 저장!)
      2. set에 반복문을 돌면서 남아있는 카드를 한개씩 뒤집습니다. (bfs로 해당 카드까지 이동)
      3. 이제 뒤집은 카드의 짝을 찾으면 되기 때문에 dfs를 호출하고 entered 파라미터에 2번에서 뒤집은 카드 번호를 넣습니다.
3. dfs가 종료되고 최종적으로 얻은 result에는 전체 이동에 필요한 조작 횟수가 담기게 됩니다.
4. 이제 result에 enter를 누른 횟수를 더해주고 리턴합니다.

 

 

 

 

마무리

처음 문제를 봤을 때 막막했었는데 한 단계씩 풀고 나니 나름 합리적이었습니다.

bfs, dfs 정도를 제외하면 특별한 알고리즘 기법은 필요 없었고 오히려 빡센 구현 문제에 가까웠습니다.

 

보통 최단거리만 물어보는 문제가 대부분인데 이 문제는 최단 거리(bfs)와 이 최단 거리를 구하는 상황을 잘 분기해서 처리(dfs부분)하는 로직이 더해져서 사실상 2 문제를 합쳐놓은 느낌이었습니다.