[Swift][BFS] 백준 16948번 (데스 나이트)

요구능력 : BFS의 사용

 

코드설명 : 

 

큐에 저장할 때 좌표와 이동횟수를 함께 저장해줬다.

좌표를 활용하는것이기 때문에 방문여부역시 2차원배열을 사용했다.

isChecked는 이동할 수 없는경우에 -1을 출력하기위해 선언하였다.

 

처음에 큐에 r1, c1이 저장되어있는 arr[0]과 arr[1] 그리고 이동횟수인 0을 넣어준다.

방문처리를 해주고 큐에 있는걸 꺼내준다.

큐에서 꺼내준 r과 c가 r2(arr[2]), c2(arr[3])과 같다면 이동이 끝났으므로 이동횟수인 pop.1을 출력해준다.

 

그 후 아래에는 문제에 적혀있는데로 최소한의 조건을  만족하면이동할 수 있는 곳으로 이동할 수 있도록 처리해준다.

그리고 isChecked가 그대로 true이면 이동할 수 없는 경우이므로 -1을 출력해준다.

 

후기 : 기본적인 BFS문제인 것 같다.

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var queue = [([Int], Int)]()
var visited = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)
var isChecked = true
func bfs(){
    queue.append(([arr[0],arr[1]],0))
    visited[arr[0]][arr[1]] = true
    while !queue.isEmpty{
        //pop.0[0] = r
        //pop.0[1] = c
        let pop = queue.removeFirst()
        if pop.0[0] == arr[2] && pop.0[1] == arr[3]{
            print(pop.1)
            isChecked = false
            break
        }
        
        if pop.0[0] - 2 >= 0 && pop.0[0] - 2 < n{
            if  pop.0[1] - 1 >= 0 && pop.0[1] - 1 < n && !visited[pop.0[0] - 2][pop.0[1] - 1]{
                visited[pop.0[0] - 2][pop.0[1] - 1] = true
                queue.append(([pop.0[0] - 2,pop.0[1] - 1],pop.1 + 1))
            }
            if  pop.0[1] + 1 >= 0 && pop.0[1] + 1 < n && !visited[pop.0[0] - 2][pop.0[1] + 1]{
                visited[pop.0[0] - 2][pop.0[1] + 1] = true
                queue.append(([pop.0[0] - 2,pop.0[1] + 1],pop.1 + 1))
            }
        }
        
        if pop.0[0] >= 0 && pop.0[0] < n{
            if  pop.0[1] - 2 >= 0 && pop.0[1] - 2 < n && !visited[pop.0[0]][pop.0[1] - 2]{
                visited[pop.0[0]][pop.0[1] - 2] = true
                queue.append(([pop.0[0],pop.0[1] - 2],pop.1 + 1))
            }
            if  pop.0[1] + 2 >= 0 && pop.0[1] + 2 < n && !visited[pop.0[0]][pop.0[1] + 2]{
                visited[pop.0[0]][pop.0[1] + 2] = true
                queue.append(([pop.0[0],pop.0[1] + 2],pop.1 + 1))
            }
        }
        
        if pop.0[0] + 2 >= 0 && pop.0[0] + 2 < n{
            if  pop.0[1] - 1 >= 0 && pop.0[1] - 1 < n && !visited[pop.0[0] + 2][pop.0[1] - 1]{
                visited[pop.0[0] + 2][pop.0[1] - 1] = true
                queue.append(([pop.0[0] + 2,pop.0[1] - 1],pop.1 + 1))
            }
            if  pop.0[1] + 1 >= 0 && pop.0[1] + 1 < n && !visited[pop.0[0] + 2][pop.0[1] + 1]{
                visited[pop.0[0] + 2][pop.0[1] + 1] = true
                queue.append(([pop.0[0] + 2,pop.0[1] + 1],pop.1 + 1))
            }
        }
    }
    if isChecked{
        print(-1)
    }
    
}
bfs()