[Swift][BFS] 백준 7562번 (나이트의 이동)

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

문제를 읽어보면 움직이려는 칸의 이미지를 보면 BFS로 찾으라는거 같고, 최소 몇번만에 이동할 수 있는지라는 지문에서 BFS임을 확신했다.

그래서 조건을 찾아보면

1. 체스판의 각 칸은 두 수의 쌍 {0 ~ l-1 } * {0 ~ l-1}

2. 한번에 이동할 수 있는 칸

다른 BFS문제들과 마찬가지로 최소값을 찾기위해서는 반드시 방문처리를 해줘야하고 queue를 이용하여 문제를 풀었다.

 

queue를 3가지 튜플로 구성했다.

1번째는 현재있는 칸의 x좌표, 2번째는 현재있는 칸의 y좌표, 3번째는 이동횟수

방문횟수는 어차피 체스판의 최대가 300 * 300이기 때문에 300개씩 잡아줬다.

그리고 이 문제에서 다른 BFS문제들과 차별점은 테스트케이스로 여러번 돌려준다는것이다.

만약 큐와 방문배열을 초기화해주지 않는다면 큐는 돌다가 남아있는 큐가 존재할 것이고 방문배열은 다음번 테스트케이스를 실행할 때 이미 방문처리가 되있어서 실행이 되지않는다.

let t = Int(String(readLine()!))!
var queue: [(Int, Int, Int)] = []
var visited = Array(repeating: Array(repeating: false, count: 300), count: 300)
for _ in 1...t{
    let l = Int(String(readLine()!))!
    let now = readLine()!.split(separator: " ").map{Int(String($0))!}
    let destination = readLine()!.split(separator: " ").map{Int(String($0))!}
    bfs(now, destination, l)
    queue = []
    visited = Array(repeating: Array(repeating: false, count: 300), count: 300)
}

 

pop.0, pop.1, pop.2는 위에서 설명한 튜플의 순서이다.

나는 크게 4가지로 조건을 나눠서 문제를 풀었다.

1. y좌표가 2칸 올라가는경우

-> x좌표가 1칸 오른쪽으로 이동하는경우

-> x좌표가 1칸 왼쪽으로 이동하는 경우

 

2. y좌표가 2칸 내려가는경우

-> x좌표가 1칸 오른쪽으로 이동하는경우

-> x좌표가 1칸 왼쪽으로 이동하는 경우

 

3. x좌표가 2칸 오른쪽으로 이동하는 경우

-> y좌표가 1칸 올라가는 경우

-> y좌표가 1칸 내려가는 경우

 

4. x좌표가 2칸 왼쪽으로 이동하는 경우

-> y좌표가 1칸 올라가는 경우

-> y좌표가 1칸 내려가는 경우

func bfs(_ now: [Int], _ destination: [Int], _ l: Int){
    queue.append((now[0], now[1], 0))
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        //큐를 뽑았는데 큐의 x, y좌표가 목표지점의 x, y좌표와 같다면 이동횟수를 출력하고 while문을 빠져나온다.
        if (pop.0, pop.1) == (destination[0], destination[1]){
            print(pop.2)
            break
        }
        if pop.1 + 2 < l{
            if pop.0 + 1 < l && !visited[pop.0 + 1][pop.1 + 2]{
                visited[pop.0 + 1][pop.1 + 2] = true
                queue.append((pop.0 + 1, pop.1 + 2, pop.2 + 1))
            }
            
            if pop.0 - 1 >= 0 && !visited[pop.0 - 1][pop.1 + 2]{
                visited[pop.0 - 1][pop.1 + 2] = true
                queue.append((pop.0 - 1, pop.1 + 2, pop.2 + 1))
            }
        }
        
        if pop.1 - 2 >= 0{
            if pop.0 + 1 < l && !visited[pop.0 + 1][pop.1 - 2]{
                visited[pop.0 + 1][pop.1 - 2] = true
                queue.append((pop.0 + 1, pop.1 - 2, pop.2 + 1))
            }
            
            if pop.0 - 1 >= 0 && !visited[pop.0 - 1][pop.1 - 2]{
                visited[pop.0 - 1][pop.1 - 2] = true
                queue.append((pop.0 - 1, pop.1 - 2, pop.2 + 1))
            }
        }
        
        if pop.0 + 2 < l {
            if pop.1 + 1 < l && !visited[pop.0 + 2][pop.1 + 1]{
                visited[pop.0 + 2][pop.1 + 1] = true
                queue.append((pop.0 + 2, pop.1 + 1, pop.2 + 1))
            }
            
            if pop.1 - 1 >= 0 && !visited[pop.0 + 2][pop.1 - 1]{
                visited[pop.0 + 2][pop.1 - 1] = true
                queue.append((pop.0 + 2, pop.1 - 1, pop.2 + 1))
            }
        }
        
        if pop.0 - 2 >= 0 {
            if pop.1 + 1 < l && !visited[pop.0 - 2][pop.1 + 1]{
                visited[pop.0 - 2][pop.1 + 1] = true
                queue.append((pop.0 - 2, pop.1 + 1, pop.2 + 1))
            }
            
            if pop.1 - 1 >= 0 && !visited[pop.0 - 2][pop.1 - 1]{
                visited[pop.0 - 2][pop.1 - 1] = true
                queue.append((pop.0 - 2, pop.1 - 1, pop.2 + 1))
            }
        }
    }
}

 

 

 

후기 : 조건이 나름 쉬운문제이다.

let t = Int(String(readLine()!))!
var queue: [(Int, Int, Int)] = []
var visited = Array(repeating: Array(repeating: false, count: 300), count: 300)
for _ in 1...t{
    let l = Int(String(readLine()!))!
    let now = readLine()!.split(separator: " ").map{Int(String($0))!}
    let destination = readLine()!.split(separator: " ").map{Int(String($0))!}
    bfs(now, destination, l)
    queue = []
    visited = Array(repeating: Array(repeating: false, count: 300), count: 300)
}

func bfs(_ now: [Int], _ destination: [Int], _ l: Int){
    queue.append((now[0], now[1], 0))
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if (pop.0, pop.1) == (destination[0], destination[1]){
            print(pop.2)
            break
        }
        if pop.1 + 2 < l{
            if pop.0 + 1 < l && !visited[pop.0 + 1][pop.1 + 2]{
                visited[pop.0 + 1][pop.1 + 2] = true
                queue.append((pop.0 + 1, pop.1 + 2, pop.2 + 1))
            }
            
            if pop.0 - 1 >= 0 && !visited[pop.0 - 1][pop.1 + 2]{
                visited[pop.0 - 1][pop.1 + 2] = true
                queue.append((pop.0 - 1, pop.1 + 2, pop.2 + 1))
            }
        }
        
        if pop.1 - 2 >= 0{
            if pop.0 + 1 < l && !visited[pop.0 + 1][pop.1 - 2]{
                visited[pop.0 + 1][pop.1 - 2] = true
                queue.append((pop.0 + 1, pop.1 - 2, pop.2 + 1))
            }
            
            if pop.0 - 1 >= 0 && !visited[pop.0 - 1][pop.1 - 2]{
                visited[pop.0 - 1][pop.1 - 2] = true
                queue.append((pop.0 - 1, pop.1 - 2, pop.2 + 1))
            }
        }
        
        if pop.0 + 2 < l {
            if pop.1 + 1 < l && !visited[pop.0 + 2][pop.1 + 1]{
                visited[pop.0 + 2][pop.1 + 1] = true
                queue.append((pop.0 + 2, pop.1 + 1, pop.2 + 1))
            }
            
            if pop.1 - 1 >= 0 && !visited[pop.0 + 2][pop.1 - 1]{
                visited[pop.0 + 2][pop.1 - 1] = true
                queue.append((pop.0 + 2, pop.1 - 1, pop.2 + 1))
            }
        }
        
        if pop.0 - 2 >= 0 {
            if pop.1 + 1 < l && !visited[pop.0 - 2][pop.1 + 1]{
                visited[pop.0 - 2][pop.1 + 1] = true
                queue.append((pop.0 - 2, pop.1 + 1, pop.2 + 1))
            }
            
            if pop.1 - 1 >= 0 && !visited[pop.0 - 2][pop.1 - 1]{
                visited[pop.0 - 2][pop.1 - 1] = true
                queue.append((pop.0 - 2, pop.1 - 1, pop.2 + 1))
            }
        }
    }
}