[백준] (Swift) 2178번 - 미로탐색 (BFS 풀이)

💻 문제 링크

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

2178번: 미로 탐색

 

💻 문제 풀이

기본적이 BFS 문제이다. 미로를 가중치 없는 무방향 그래프로 본다면, 가중치없는 무방향 그래프에서 최단거리를 구하는 BFS 탐색 방법을 이용하면된다!

• 처음 입력받는 n과 m을 nm 배열로 입력받아서 nm[0], nm[1] 로 사용하였다. 
• dx, dy 는 상하좌우 방향을 나타내는 방향키! 이다.
• arr는 입력받는 미로
• visited는 미로에서 방문했는지 안했는지 T/F 로 나타내는 배열
• distance는 최단거리를 구할때 하나씩 +1 해서 마지막에 distance[n][m]으로 답을 출력해 줄 것이다.

기본적인 bfs 문제로 더이상 queue가 존재하지 않을때까지 while문을 돌려서 답을 구할 수 있다.

 

💻 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2178_%EB%AF%B8%EB%A1%9C%ED%83%90%EC%83%89/main.swift

GitHub - deslog/Algorithm

//
//  File.swift
//  Algorithm
//
//  Created by 이지수 on 2022/06/23.
//

var nm = readLine()!.split(separator: " ").map { Int(String($0))! }

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0] // 상하좌우

var arr = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: nm[1]), count: nm[0])
var distance = Array(repeating: Array(repeating: 0, count: nm[1]), count: nm[0])

for _ in 0..<nm[0] {
    var temp = Array(readLine()!).map { Int(String($0))! }
    arr.append(temp)
}

func bfs() {
    distance[0][0] = 1
    visited[0][0] = true
    
    var queue: [[Int]] = [[0,0]]
    
    while !queue.isEmpty {
        let pop = queue.removeFirst()
        
        let x = pop[0]
        let y = pop[1]
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx >= 0 && nx < nm[0] && ny >= 0 && ny < nm[1] {
                if !visited[nx][ny] && arr[nx][ny] == 1 {
                    distance[nx][ny] = distance[x][y] + 1
                    
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }
            }
        }
    }
}

bfs()
print(distance[nm[0]-1][nm[1]-1])