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

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

최소의 이동을 요구하는 문제는 BFS로 접근하는게 맞는것같다.

DFS로도 풀 수는 있지만 DFS는 모든 경우의수를 다 돌아보기 때문에 자칫하면 시간초과가 날 수 있다.

이 문제는 문제에서 최소의 이동을 요구했기 때문에 BFS로 풀어볼 것이다.

 

1. n,m 과 좌표의 크기 받기

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (nm[0], nm[1])

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

 

2. 큐 선언, 상,하,좌,우로 이동하기위한 배열 선언

큐에는 x,y좌표를 저장하기 위해 튜플을 사용할것이다.

var queue = [(0, 0)]
let (dx, dy) = ([-1, 1, 0, 0], [0,0,1,-1])

 

3. BFS진행

(참고 : 이번에 removeFirst()의 존재를 처음 알았는데, 배열에[a, b, c, d]가 있으면 a를 리턴해주고 배열을 앞으로 당겨서 [b, c, d]로 만들어준다. 굳이 queue를 따로 구현할 필요가 없었다....)

 

queue에는 배열안에 튜플이 있는 형태로 저장되어있기 때문에 원소를 빼면 튜플의 형태이다.

그렇기에 튜플의 형태로 받아주고,

상하좌우를 다 확인하기 위해서 반복문은 4번 돌아준다.

while !queue.isEmpty {
    let (x, y) = queue.removeFirst()
    
    for i in 0..<4 {
        let nx = x + dx[i], ny = y + dy[i] //nx, ny는 변경하기위한 좌표
        if nx < 0 || ny < 0 || nx >= n || ny >= m {continue}// nx와 ny가 배열밖으로 넘어가는것을 방지
        if arr[nx][ny] == 0 {continue} //1일때만 이동가능하기 때문에 0일떄는 넘긴다.
        if arr[nx][ny] == 1 {
            arr[nx][ny] = arr[x][y] + 1 //nx, ny로 이동하기 전의 위치에 1을 더해서 삽입(누적되면 최종값이된다.)
            //이렇게 하면 자연스럽게 이미 방문한 좌표는 1이 아니기 때문에 재방문하지 않는다.
            
            queue.append((nx, ny))//네 방향중 arr이 1이 들어간 곳만 큐에 추가
            }
            
        }
}

 

 

후기 : 이런방법으로도 풀리는구나 싶었고 BFS를 공부하기에 아주 적합한 문제인거 같다.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (nm[0], nm[1])

var arr = [[Int]]()
for _ in 0..<n {
    arr.append(readLine()!.map{Int(String($0))!})
}
var queue = [(0, 0)]
let (dx, dy) = ([-1, 1, 0, 0], [0,0,1,-1])

while !queue.isEmpty {
    let (x, y) = queue.removeFirst()
    for i in 0..<4 {
        let nx = x + dx[i], ny = y + dy[i]
        if nx < 0 || ny < 0 || nx >= n || ny >= m {continue}
        if arr[nx][ny] == 0 {continue}
        if arr[nx][ny] == 1 {
            arr[nx][ny] = arr[x][y] + 1
            queue.append((nx, ny))
            }
            
        }
}
print(arr[n - 1][m - 1])