[Swift] BOJ 2178 미로 탐색

BOJ 2178 미로 탐색

 

✅ BFS 문제였다.

DFS의 경우에는 하나의 노드를 깊게 탐색하여 그 노드가 최선값이 아니면 기회비용이 더 들어간다.

그리고 나동빈 책에서도 DFS보다 BFS가 일반적인 코딩테스트에서 더 빠르다고 권장함.

 

일단 BFS에 아직 익숙치 않아서 어려웠음.

그동안 문제 풀면서 가장 어려웠던 유형이 이렇게 N x M 배열에서 무언가 최선의 값을 구하거나 경로를 구하는 등의 작업이면 진짜 힘들었음.

나름의 방법으로 해결하겠다고 한 것이 재귀를 이용하여 풀어보려는 시도를 아주 많이 해보았으나, 대부분 fail.

BFS 공부는 진짜 많이 했는데, 적용이 도저히 안되겠어서 구글링의 도움을 받아 적용시켜봄

 

✅ 알고리즘 순서 

1. queue에 시작점을 세팅한다.

2. 현재위치에서 상하좌우 4번의 이동이 가능하므로 for문을 돌면서 다음번 이동 가능한 위치(nx,ny)값을 구한다.

3. 조건문을 사용하여 총 이동거리를 찾는다.

if (보드안에 다음번 좌표가 위치한다.) && (이전에 방문했던 장소가 아니다.) { 
    if (보드의 좌표가 이동 가능한 값(1)이다.) { 
        1. 큐에 이동 가능한 위치를 넣어준다.
        2. 총 이동 거리를 계산한다.
        3. 방문한 좌표를 true로 변경한다.
    }
}

내부 if문에서 총 이동 거리를 계산하는 2번이 핵심이다.

총 이동 거리를 계산하는 방법은 보드의 다음 위치에 현재 위치값 + 1을 해주면 된다.

현재 위치값은 이동을 하면서 항상 갱신이 되므로 걱정하지 않아도 된다.

 

 

 

🟠 코드

//https://www.acmicpc.net/problem/2178
import Foundation

struct b2178 {
    static func run() {
        // Input 처리
        let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
        var board = [[Int]](repeating: [], count: input[0])
        
        for i in 0..<input[0] {
            let v = readLine()!.map { Int("\($0)")! }
            board[i].append(contentsOf: v)
        }
//        print(board)
        
        // 상화좌우 세팅
        let dx = [-1, 1, 0, 0]
        let dy = [0, 0, -1, 1]
        
        var queue = [[0,0]] // 큐
        var visited = [[Bool]](repeating: [Bool](repeating: false, count: input[1]), count: input[0]) // 방문했는지 확인
        
        var nx = 0
        var ny = 0
        
        // 시작좌표 세팅
        var x = queue[0][0]
        var y = queue[0][1]
        visited[0][0] = true
        
        while !queue.isEmpty {
            x = queue[0][0]
            y = queue[0][1]
            
            queue.removeFirst() // append로 넣을 것이라서 FIFO 적용
            
            for i in 0..<4 {
                // 이동 가능한 좌표 계산
                nx = x + dx[i]
                ny = y + dy[i]
                
                // 좌표가 board의 좌표를 벗어나지 않으면
                if nx >= 0 && ny >= 0 && nx < input[0] && ny < input[1] && visited[nx][ny] == false {
                    if board[nx][ny] == 1 {
                        queue.append([nx, ny])
                        board[nx][ny] = board[x][y] + 1 // 총 이동거리 계산
                        visited[nx][ny] = true // 방문한 곳은 true로 변경
//                        print("-> \(queue) \n -> \(board)")
                    }
                }
            }
        }
        print(board[input[0]-1][input[1]-1])
    }
}