[프로그래머스] Swift - 블록 이동하기

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

프로그래머스

 

2023.08.30 기준 Level 3

 

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

 

아이디어

2차원 배열을 이동하며 목적지까지의 최단 비용을 찾는 문제입니다.

 

이와 유사한 문제는 많이 겪어 봤고 BFS를 활용해야 한다는 것 또한 알고 있었습니다.

그럼에도 이 문제가 많이 어렵게 느껴진 이유는 이동하는 로봇의 크기가 1x1이 아니라 2x1사이즈이며 심지어 회전도 가능하기 때문에 고려해야 하는 경우의 수가 급격하게 늘었기 때문입니다.

 

일반적인 BFS 탐색 문제 풀이 순서

1. 큐 생성
2. 큐에 현재 좌표 넣기
3. 큐에 남은 요소가 없을 때까지 반복문을 돌며 첫번째 요소 Dequeue
4. 3번에서 얻은 요소(좌표)에서 이동할 수 있는 다음 좌표들을 Enqueue (한번 방문한 곳은 재방문하지 않도록 분기처리)
5. 3~4번을 반복하며 목적지에 도달하면 break

이러한 구조로 풀게 됩니다.

이 문제도 마찬가지지만 로봇의 크기가 2x1이고 회전 가능 때문에 4번 과정을 구현하는 것이 빡세졌습니다.

 

현재 좌표에서 이동할 수 있는 다음 좌표를 구할 때 로봇이 2개의 좌표를 차지하기 때문에 좌표를 2개씩 묶어서 구현해야 하며 회전 때문에 현재 로봇 위치에서 회전할 수 있는 모든 경우를 다 구해야 합니다.

 

고려해야 하는 이동 방향

1. 위로 이동
2. 아래로 이동
3. 왼쪽으로 이동
4. 오른쪽으로 이동
5. 회전
   
   • 로봇이 가로일 때
     • 왼쪽 날개를 회전축으로 둘 때
       
       1. 시계 방향 이동
       2. 반시계 방향 이동
     • 오른쪽 날개를 회전축으로 둘 때
       1. 시계 방향 이동
       2. 반시계 방향 이동
   • 롯봇이 세로일 때
     • 위쪽 날개를 회전축으로 둘 때
       
       1. 시계 방향 이동
       2. 반시계 방향 이동
     • 아래쪽 날개를 회전축으로 둘 때
       1. 시계 방향 이동
       2. 반시계 방향 이동

이렇게 총 12개의 경우의 수를 전부 구해서 큐에 넣어줘야 합니다.

배열의 특성상 index out of range 문제가 발생하지 않도록 범위도 체크해주고 벽이 있는지 또한 체크해주면서 12개의 위치를 전부 찾아서 넣어줘야 한다는 의미입니다. (매우 귀찮은 빡구현 문제가 되었습니다...)

물론, 다른 창의적은 방식으로 이동 가능한 위치들을 멋지게 찾을 수도 있겠지만 제가 생각나는 방식은 이렇게 각 경우의 수를 직접 찾는 것이었습니다. (다른 분들도 이와 유사하게 푸신 분들이 제일 많은 것 같습니다.)

 

풀이

1. RobotCoordinate 구조체 생성

fileprivate typealias Coordinate = (x: Int, y: Int)

fileprivate struct RobotCoordinate {
    var wing1: Coordinate
    var wing2: Coordinate
    var cost = 0
    
    var leftPosition: Coordinate {
        [wing1, wing2].sorted { $0.y < $1.y }[0]
    }
    
    var rightPosition: Coordinate {
        [wing1, wing2].sorted { $0.y < $1.y }[1]
    }
    
    var topPosition: Coordinate {
        [wing1, wing2].sorted { $0.x < $1.x }[0]
    }
    
    var bottomPosition: Coordinate {
        [wing1, wing2].sorted { $0.x < $1.x }[1]
    }
    
    var isHorizontal: Bool {
        return wing1.x == wing2.x
    }
    
    var toString: String {
        return "\(leftPosition.x),\(leftPosition.y),\(rightPosition.x),\(rightPosition.y)"
    }
}

문제의 조건에서 로봇이 2x1 크기이기 때문에 한 로봇이 2개의 좌표를 가지게 됩니다. (각 날개가 좌표를 1개씩 할당)

좌표 2개를 담는 RobotCoordinate 구조체를 생성했습니다. 

이렇게 객체화하지 않고 직접 좌표를 튜플이나 어레이로 다뤄도 상관 없습니다만 이게 더 깔끔할 것 같아서 구조체를 생성했습니다.

 

typealias로 Coordinate가 (x, y) 형태의 튜플을 나타내도록 했습니다.

 

leftPosition은 로봇의 2 좌표 중에 더 왼쪽에 위치한 좌표를 의미합니다.

rightPosition은 반대로 더 우측에 위치한 좌표를 의미합니다.

topPosition은 더 위에 위치한 좌표를 의미합니다.

bottomPosition은 더 아래에 위치한 좌표를 의미합니다.

 

로봇이 세로로 위치했다면 leftPosition이나 rightPosition을 사용하지 않고 topPosition과 bottomPosition을 사용하여 2개의 좌표를 구분하면 됩니다.

 

cost는 이 위치까지 도착했을 때 필요한 비용을 의미합니다. (정답 도출에 필요)

 

 

2. findMovablePositions 함수 구현

fileprivate func findMovablePositions(board: [[Int]], cur: RobotCoordinate) -> [RobotCoordinate] {
    
    func canMove(coord: Coordinate) -> Bool {
        return board[coord.x][coord.y] == 0
    }
    
    let n = board.count
    
    var movablePositions = [RobotCoordinate]()
    
    let curLeft = cur.leftPosition      // 로봇의 왼쪽 날개
    let curRight = cur.rightPosition    // 로봇의 오른쪽 날개
    let curTop = cur.topPosition        // 로봇의 위쪽 날개
    let curBottom = cur.bottomPosition  // 로봇의 아래쪽 날개
    
    // 좌
    if curLeft.y >= 1 && canMove(coord: (curLeft.x, curLeft.y-1))
        && canMove(coord: (curRight.x, curRight.y-1)) {
        movablePositions.append(RobotCoordinate(wing1: (curLeft.x, curLeft.y-1),
                                                wing2: (curRight.x, curRight.y-1)))
    }
    
    // 우
    if curRight.y < n-1 && canMove(coord: (curLeft.x, curLeft.y+1))
        && canMove(coord: (curRight.x, curRight.y+1)) {
        movablePositions.append(RobotCoordinate(wing1: (curLeft.x, curLeft.y+1),
                                                wing2: (curRight.x, curRight.y+1)))
    }
    
    // 상
    if curTop.x >= 1 && canMove(coord: (curTop.x-1, curTop.y))
        && canMove(coord: (curBottom.x-1, curBottom.y)) {
        movablePositions.append(RobotCoordinate(wing1: (curTop.x-1, curTop.y),
                                                wing2: (curBottom.x-1, curBottom.y)))
    }
    
    // 하
    if curBottom.x < n-1 && canMove(coord: (curBottom.x+1, curBottom.y))
        && canMove(coord: (curTop.x+1, curTop.y)) {
        movablePositions.append(RobotCoordinate(wing1: (curBottom.x+1, curBottom.y),
                                                wing2: (curTop.x+1, curTop.y)))
    }
    
    if cur.isHorizontal {
        // 왼쪽 날개를 회전축으로
        // 시계 방향
        if curLeft.x < n-1 && canMove(coord: (curRight.x+1, curRight.y)) && canMove(coord: (curLeft.x+1, curLeft.y)) {
            movablePositions.append(RobotCoordinate(wing1: curLeft, wing2: (curLeft.x+1, curLeft.y)))
        }
        
        // 반시계 방향
        if curLeft.x >= 1 && canMove(coord: (curRight.x-1, curRight.y)) && canMove(coord: (curLeft.x-1, curLeft.y)) {
            movablePositions.append(RobotCoordinate(wing1: curLeft, wing2: (curLeft.x-1, curLeft.y)))
        }
        
        // 오른쪽 날개를 회전축으로
        // 시계 방향
        if curRight.x >= 1 && canMove(coord: (curLeft.x-1, curLeft.y)) && canMove(coord: (curRight.x-1, curRight.y)) {
            movablePositions.append(RobotCoordinate(wing1: (curRight.x-1, curRight.y), wing2: curRight))
        }
        
        // 반시계 방향
        if curRight.x < n-1 && canMove(coord: (curLeft.x+1, curLeft.y)) && canMove(coord: (curRight.x+1, curRight.y)) {
            movablePositions.append(RobotCoordinate(wing1: (curRight.x+1, curRight.y), wing2: curRight))
        }
    } else {    // 수직인 상태
        // 위쪽 날개를 회전축으로
        // 시계 방향
        if curTop.y >= 1 && canMove(coord: (curBottom.x, curBottom.y-1)) && canMove(coord: (curTop.x, curTop.y-1)) {
            movablePositions.append(RobotCoordinate(wing1: curTop, wing2: (curTop.x, curTop.y-1)))
        }
        
        // 반시계 방향
        if curTop.y < n-1 && canMove(coord: (curBottom.x, curBottom.y+1)) && canMove(coord: (curTop.x, curTop.y+1)) {
            movablePositions.append(RobotCoordinate(wing1: curTop, wing2: (curTop.x, curTop.y+1)))
        }
        
        // 아래쪽 날개를 회전축으로
        // 시계 방향
        if curBottom.y < n-1 && canMove(coord: (curTop.x, curTop.y+1)) && canMove(coord: (curBottom.x, curBottom.y+1)) {
            movablePositions.append(RobotCoordinate(wing1: (curBottom.x, curBottom.y+1), wing2: curBottom))
        }
        
        // 반시계 방향
        if curBottom.y >= 1 && canMove(coord: (curTop.x, curTop.y-1)) && canMove(coord: (curBottom.x, curBottom.y-1)) {
            movablePositions.append(RobotCoordinate(wing1: (curBottom.x, curBottom.y-1), wing2: curBottom))
        }
    }
    
    return movablePositions
}

현재 위치인 cur을 받아서 해당 위치에서 움직일 수 있는 경우의 수들을 전부 구하는 함수입니다.

앞서 말한 12개의 경우의 수를 찾아서 어레이로 리턴합니다.

 

canMove 함수는 벽이 없는지 검사하는 함수입니다.

 

회전을 시킬 때는 반드시 양쪽 날개를 회전축으로 할 때를 전부 찾아야 합니다. (빼먹으면 안 됨!!!)

 

로봇이 가로일 때와 세로일 때를 나누는 것도 중요했습니다.

양쪽 날개를 각각 회전축으로 할 때 시계와 반시계 방향으로 회전시켜야 하는데 로봇이 가로일 때는 좌, 우로 날개를 구분하면 되지만 세로 일 때는 좌우 구분이 불가능하기 때문에 이 경우에는 상, 하로 날개를 구분해서 회전축을 지정했습니다.

 

3. solution 함수 구현

fileprivate func solution(_ board:[[Int]]) -> Int {
    let n = board.count
    var visited = Set<String>()
    
    var queue = [RobotCoordinate]()
    queue.append(RobotCoordinate(wing1: (0,0), wing2: (0,1), cost: 0))
    
    while !queue.isEmpty {
        let cur = queue.removeFirst()

        let movablePositions = findMovablePositions(board: board, cur: cur)
        
        if cur.wing1 == (n-1, n-1) || cur.wing2 == (n-1, n-1) {
            return cur.cost
        }
        
        for _position in movablePositions {
            var position = _position
            if !visited.contains(position.toString) {
                position.cost = cur.cost + 1
                queue.append(position)
                visited.insert(position.toString)
            }
        }
    }

    return -1
}

이 부분은 일반적인 BFS 풀이와 같습니다.

 

큐에 좌표(RobotCoordinate)를 넣고 반복문을 돌며 Dequeue합니다.

목적지에 도착했다면 cost를 리턴합니다.

문제 조건에서 모든 테스트케이스가 반드시 목적지까지 도착할 수 있다고 제시했기 때문에 마지막에 있는 return -1은 실행되지 않습니다.

 

1가지 중요했던 것이 있습니다

바로 visited 집합입니다.

BFS에서 한번 방문한 노드를 재방문하지 않도록 하기 위해 visited 배열 혹인 집합 등을 사용하는데 여기서 visited의 타입을 Set<String>으로 선언했습니다.

 

좌표의 방문 여부를 찾아야 하는데 왜 String으로 했냐면 Swift에서는 튜플이 Hashable하지 않기 때문입니다.

당연히 Set<RobotCoordinate>로 선언하면 편리하겠지만 RobotCoordinate는 2개의 좌표를 담고 있고 이 좌표가 각각 (Int, Int) 타입의 튜플입니다.

튜플은 기본적으로 Hashable하지 않기 때문에 Set<RobotCoordinate>로 선언하면 컴파일 에러가 발생합니다.

물론 Hashable을 직접 채택시키고 hash함수를 구현하면 되지만 그렇게 하는 것이 더 비효율적이라고 판단했습니다.

 

따라서, Set<String>으로 선언하고 key값이 될 String에 좌표 정보를 넣도록 했습니다. (약간의 꼼수..ㅎㅎ)

RobotCoordinate 구조체에

    var toString: String {
        return "\(leftPosition.x),\(leftPosition.y),\(rightPosition.x),\(rightPosition.y)"
    }

이렇게 좌표를 문자열로 변환하는 변수를 만들었습니다.

 

이 값을 집합에 넣어서 중복 방문인지를 검사하도록 했습니다.

처음에는 "\(leftPosition.x),\(leftPosition.y),\(rightPosition.x),\(rightPosition.y)" 이렇게 toString을 만들었는데 10, 12의 테스트케이스에서 실패했습니다.

 

만약 로봇이 (9, 11), (9, 10) 라는 좌표를 가진다면 문자로 바꿨을 때 "911910"가 됩니다.

하지만 이 값은 (91, 1), (91,0) 을 문자열로 바꾼 값과 같게 됩니다. 

즉, Hash함수의 키 값이 중복되는 문제가 생겨서 방문하지 않은 RobotCoordinate이지만 방문한 곳이라고 분기처리되어 걸러지기 때문에 테스트케이스에서 실패하는 것이었습니다.

 

따라서 이러한 문제가 발생하지 않도록 각 좌표 사이에 ,를 넣어 구분시켜서 toString의 결과가 중복되지 않도록 했습니다.

 

 

마무리

개인적으로 매우 어렵게 느껴졌습니다.

BFS문제에서 난이도를 확 높여서 빡구현이 더해졌고 시간 초과를 해결하기 위해 Set까지 사용해야 했습니다.

로봇 회전 때문에 계속 그림 그려가며 경우의 수를 찾아서 문제를 풀었습니다.

풀고나니 기분은 좋네요...하하 😂