[프로그래머스] Swift - 미로 탈출 명령어

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

프로그래머스

 

2023.08.22 기준 Level 3

 

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

 

아이디어

• n x m 격자 미로 제공
• (x, y)에서 출발해 (r, c)로 도착해야 함
• 이동 거리가 총 k여야 함
• 같은 곳을 여러번 방문 가능
• 탈출한 경로를 문자열로 나타냈을 때 사전 순으로 가장 빠른 경로를 리턴
• 위의 조건을 따르는데 탈출이 불가능 할 경우 "impossible" 리턴

흔한 탐색 문제에 난이도를 높이는 여러 장치들을 추가한 문제였습니다...!

1. 이동 거리가 K로 고정
2. 탈출한 경로 중에서 사전 순으로 가장 빠른 경우를 찾아야 함

우선 탈출이 아예 불가능한 경우부터 처리가 가능했습니다.

k는 이동 가능한 기회의 수라고 보면 됩니다.

출발지로부터 도착지까지의 최단 거리가 d라고 하면 d-k가 음수이면 이동해야 하는 거리보다 기회가 적은 것이기 때문에 이경우 impossible을 리턴하면 됩니다

 

1가지 더 경우가 있는데 바로 (k-d)가 홀수인 경우입니다.

왜냐하면 목적지까지 최단거리로 이동시키고 우리가 임의로 남은 기회만큼 특정 거리를 왔다갔다 하여 K를 채울 수 있는데 k-d가 홀수인 경우에는 목적지에 도착한 후에 다른 위치로 보냈다가 다시 돌아오는 것이 불가능하기 때문입니다.

예를 들자면 목적지에 도착했고 기회가 2번 남았다면 아래 칸으로 보냈다가 다시 위로 올리면 목적지로 돌아오면서 모든 K를 소진시킬 수 있습니다.

반면, 목적지에 도착했고 기회가 3번 남았다면 아래칸으로 보냈다가 다시 위로 올려 목적지로 돌아와도 1번의 기회를 소진해야 하기 때문에 정답 도출이 불가능합니다.

이 경우에는 impossible을 리턴하면 됩니다.

 

이제 사전 순이라는 요구 사항을 만족시키는 아이디어를 찾으면 됩니다.

• l: 왼쪽 이동
• r: 오른쪽 이동
• u: 위쪽 이동
• d: 아래쪽 이동

이 알파벳들로 코스가 구성됩니다.

이 것들을 사전 순으로 정렬하면 d, l, r, u 입니다.

즉, d, l, r, u 에서 최대한 앞쪽에 있는 방향들로 많이 보내면서 목적지에 도착해야 한다는 의미입니다.

 

이 아이디어와 델타탐색을 사용한 bfs의 특성을 결합하면 됩니다.

bfs는 너비 우선 탐색이기 때문에 최단 경로를 찾을 수 있습니다.

이 때 델타 탐색을 활용하게 되는데 상하좌우 순서로 탐색하는 것이 아니라 d, l, r, u 순서로 탐색하는 것입니다.

즉, 하좌우상 순으로 탐색한다는 의미입니다.

단순히 이렇게 탐색을 전부 하는 것이 아니라 Queue에 하좌우상 순서로 넣는데 1개만 넣고 break를 넣어서 멈추게 합니다.

즉 dd가 가능한데 dl을 굳이 탐색을 할 필요가 없기 때문입니다. (dd가 사전 순으로 더 앞서기 때문)

 

만약 탐색하고지 하는 위치까지 온 거리 (cnt+1)과 해당 위치에서 목적지까지의 거리를 더했을 때 k보다 크다면 너무 멀리와서 k의 기회안에 목적지에 도착할 수 없는 상황이기 때문에 Queue에 넣지 않습니다.

 

풀이

fileprivate func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    func distanceToEnd(x: Int, y: Int) -> Int {
        return abs(x-r) + abs(y-c)
    }
    
    let distanceFromStartToEnd = distanceToEnd(x: x, y: y)
    
    if k - distanceFromStartToEnd < 0 || (k - distanceFromStartToEnd) % 2 != 0 {
        return "impossible"
    }
   
    // 사전 순
    let directions = ["d", "l", "r", "u"]
    let dx = [1, 0, 0, -1]
    let dy = [0, -1, 1, 0]
    
    // bfs
    var queue = [(x: Int, y: Int, course: String, cnt: Int)]()
    queue.append((x, y, "", 0))
    
    while !queue.isEmpty {
        let (x, y, course, cnt) = queue.removeFirst()
        
        if (x, y) == (r, c) && cnt == k {
            return course
        }
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            let nextCourse = course + directions[i]
            
            // 너무 멀리 와서 목적지까지의 최단 거리가 k보다 커지는 경우 -> 종료 조건
            if distanceToEnd(x: nx, y: ny) + cnt + 1 > k {
                continue
            }
            
            if nx >= 1 && nx <= n && ny >= 1 && ny <= m {
                queue.append((nx, ny, nextCourse, cnt+1))
                break
            }
        }
    }
    
    return "impossible" // 여기까지 오는 경우는 없음
}

앞서 아이디어에 적은 것처럼 impossible한 상황을 먼저 O(1)로 찾아서 끝냅니다.

이후에는 impossible을 배제해도 됩니다.

 

directions, dx, dy를 선언한 방식이 중요합니다. 꼭 저렇게 d, l, r, u로 선언하고 dx와 dy도 이 방향 순서에 맞게 설정해야 합니다.

Queue에 넣는 요소에 course는 해당 위치까지의 경로를 의미하고 cnt는 이동 횟수입니다. (course.count와 같습니다.)

 

Queue에 새 요소를 append 한 하고 for문을 break하는 것이 중요했습니다.

이렇게 안하면 시간 초과가 발생합니다.

이미 사전 순대로 directions, dx, dy를 정렬했기 때문에 먼저 큐에 한 녀석을 넣으면 그 뒤는 사전 순에서 밀리기 때문에 굳이 탐색할 필요가 없기 때문입니다!

혹시 이렇게 break를 걸어서 이후에 좌표들을 큐에 넣지 않으면 정답인 경우를 놓치지 않을까 걱정할 수 있지만 그런 경우는 존재하지 않습니다.

 

이미 앞선 조건문에서 nx, ny에서 목적지까지 도착이 가능한지 파악을 하고 있습니다. 불가능하다면 큐에 넣지 않고 continue를 시키고 있기 때문에 큐에 들어갔다는 것은 목적지까지 무조건 도착이 가능한 좌표라는 것입니다.

"dd~~~"와 "dl~~~" 둘다 목적지까지 도착한 경로라고 했을 때 "dd~~~"이 "dl~~~"보다 무조건 사전 순으로 앞서기 때문에 뒤에 ~에 어떤 방향이 오는지 상관 없이 "dd~~~"만 더 탐색하고 "dl~~~"은 제외하는 것입니다.

 

마무리

정답 코드만 보면 생각보다 단순한 탐색 문제 처럼 보이지만 디테일한 아이디어가 필요했습니다.

 

1. 델타 탐색의 방향들을 미리 정렬해두기

2. 좌표들을 큐에 넣을 때 1개만 넣고 break 시키기

 

이러한 것들을 생각해내는 것이 꽤 어려워서 저도 질문하기 탬에서 힌트를 받았습니다.