[Swift] BOJ 2178 미로 탐색

BOJ 2178 미로 탐색

 

접근 방식

 

최단 경로를 구하는 BFS 문제. 시작 칸에서 상하좌우로 한 겹씩 퍼지므로, 도착 칸에 처음 닿는 순간이 최단 거리가 됨.

 

N x M 격자에서 최단 경로를 재귀(DFS)로 접근하면 먼저 닿은 경로가 최단이라는 보장이 없어, 여러 번 시도했지만 통과하지 못하고 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])
    }
}