[Swift] 백준 2178 - 미로탐색

문제 바로가기

해당 위치에서 상,하,좌,우로 이동할 수 있는지를 확인하고
또 이동가능한 최단 거리를 구하여야하는 문제이다.

상,하,좌,우로 이동할 수 있는지 확인은 BFS로 하면 되는데
최단거리를 어떻게 구할 지가 고민이였다.

처음엔, BFS로 구한 이동 가능한 위치배열과
재귀함수를 사용해서 거리를 구하였다.

초기풀이 (시간초과됨)

import Foundation

let line = readLine()!.split(separator: " ").map {Int(String($0))!}
let N = line[0]
let M = line[1]

var graph = [[Int]]()
var needToVisit = [(Int,Int)]()
var needToRecur = [(Int,Int)]()

for _ in 0..<N {
    let nums = Array(readLine()!).map{Int(String($0))!}
    graph.append(nums)
}

func bfs(_ r: Int, _ c: Int) {
    needToVisit.append((r,c))
    needToRecur.append((r,c))
    graph[r][c] = 0
    
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        
        for i in [(1,0),(-1,0),(0,1),(0,-1)] {
            let (nx,ny) = (node.0 + i.0, node.1 + i.1)
            
            if (0..<N).contains(nx) && (0..<M).contains(ny) && graph[nx][ny] == 1 {
                graph[nx][ny] = 0
                needToVisit.append((nx,ny))
                needToRecur.append((nx,ny))
            }
        }
    }
}

bfs(0, 0)

var minCount = Int.max
var visit : [Bool] = Array(repeating: false, count: needToRecur.count)
visit[0] = true

func recur(_ count: Int, _ now: Int) {
    if count > minCount {
        return
    }
    
    if needToRecur[now] == (N-1,M-1) {
        minCount = min(minCount, count)
        return
    }

    for i in now..<needToRecur.count {
        if (abs(needToRecur[i].0 - needToRecur[now].0) + abs(needToRecur[i].1 - needToRecur[now].1) ) < 2 {
            if !visit[i] {
                visit[i] = true
                recur(count+1, i)
                visit[i] = false
            }
        }
    }
}

recur(1, 0)
print(minCount)

억울,,

그런데 더 좋은 방법이 있었다
그냥 distance 배열을 만들어서
bfs로 상,하,좌,우 중 이동할 수 있는 위치를 찾게된다면
해당 위치의 distance에 distance[기존위치] + 1 값을 넣어주면 되는 것이다

예를들어 N = 4, M = 6 이고
각 칸의 값은 아래와 같을 때
110110
110110
111111
111101

최단거리는 다음과 같은 방식으로 구할 수 있다

최종 코드

import Foundation

let line = readLine()!.split(separator:" ").map{Int(String($0))!}
let N = line[0]
let M = line[1]

var graph = [[Int]]()

for _ in 0..<M {
    let numArr = Array(readLine()!).map{Int(String($0))!}
    graph.append(numArr)
}

var needToVisit = [(Int,Int)]()
var distance : [[Int]] = Array(repeating: Array(repeating: 0, count:N), count:M)
distance[0][0] = 1

func bfs(_ r:Int, _ c:Int) {
    needToVisit.apped((r,c))
    graph[r][c] = 0
    
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        
        for i in [(1,0),(-1,0),(0,1),(0,-1)] {
            let (nx,ny) = (node.0 + i.0, node.1 + i.1)
            
            if (0..<N).contains(nx) && (0..<M).contains(ny) && graph[nx][ny] == 1 {
                graph[nx][ny] = 0
                needToVisit.apped((nx,ny))
                distance[nx][ny] = distance[node.0][node.1] + 1 
            }
        }
    }
}

bfs(0,0)
print(distance[N-1][M-1])