[백준/Swift] 7562 : 나이트의 이동

여러분 안녕하세요

최근에 dfs&bfs 문제에 빠져서 계속 풀다가 시험기간이라.. 3주간 공부를 못해서 복습할 겸 풀어봤습니다.

---

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

7562번: 나이트의 이동

---

간단한 문제 설명부터 시작하겠습니다!!

체스판 크기가 주어져야 하고,

그위에 처음 나이트 위치가 주어집니다.

나이트가 이동할 수 있는 칸은 가운데 점을 시작점으로 총 8번 움직일 수 있습니다!

(튜플로 쉽게 ㅎㅎ,,)

let direction =[(1번 칸 좌표),(2번 칸 좌표),(3),(4)...(8번 칸 좌표)]

마지막으로 나이트가 이동해야 할 마지막 좌표가 주어집니다.

 

테스트 케이스마다 체스판의 크기 , 시작좌표에서 나이트가 한 번에 이동할 수 있는 칸을 통해 '최소한'으로 도착좌표에 도달하는 것이 이 문제입니다.

 

(TMI: 갤노트로 그림 그렸는데 잘 못그립니다. ㅠㅠ 연습해야겠어요)

 

 제가 체스를 몰라서,, 처음에 우선 한번 8*8 크기에서 나이트의 이동으로 최소점을 찾기 위해 그림으로 bfs탐색을  시도했습니다.

S는 0,0 이고, F는 7,0 입니다.

동그라미는 나이트의 이동을 표현합니다.

dfs 탐색을 통해 F까지 가는 첫번째, 두번째 경우인데 정답 최소 5와는 거리가 멀어지는게 보여서 최소 칸 도달 하는 다른 경우를 찾아야 합니다.( 계속 탐색 시  F좌표 도달하기는 합니다!!!! - 6번만에 F 지점으로 도달 할 수 있습니다.)

이번엔 분홍색으로 한칸, 녹색 경로로 두칸 이동, 황색경우로 2칸 이동을 해서 결국 '5번'이라는 나이트의 최소 이동으로 도착 지점을 찾았습니다. 

 

dfs 경우에는 모든 칸을 훑어서 도착지점을 도착하기 때문에 "최소"로 이동해야하는 이 문제를 찾기 위해선 결국 모든 경우의 탐색을 시도해야 최소 로 이동한 나이트의 횟수를 알 수 있습니다.

 

따라서 이 경우에는 Qeueu를 통한, 특정 구간의 마지막 칸 까지 탐색하는게 아닌, 동시에 탐색을 해서 특정 탐색에 F로 도달하는게 '최소'인 결과를 내는 BFS 탐색을 실행해야 합니다.

따라서 주어진 시작좌표에서 나이트가 갈 수 있는 위치로 간 경우 이전 위치에서 1만큼 이동했기에 +1을 더한 1!!

(회색) 1에서 다음 칸 2(남색)로 갈 수 있는 경우를 탐색하고,

'2'번째의 좌표에서 그 다음으로 갈 수 있는 좌표를 탐색하고

( 3) 탐색하고 (4 ) 계속해서 탐색하고 ( 5) 어?! (7,0) 좌표에- 우리가 원하는 좌표 - 도착했네요.

그럼 더 이상의 탐색은 하지않고 종료하는 것이 BFS 의 장점입니다!!! 호호 쉽습니다 여러분도 몇번만 손으로 그리고 코드 짜면 금방 쉬워질 것입니다!!

 

하지만 위의 경우에서 주의해야할 점이 있습니다. 시작좌표, 도착좌표가 (1,1) , (1,1) 인 경우, 0에서 1로 탐색한 후 다시 시작좌표로 도달하는 경우...가 있습니다. 원래 정답은 그냥 가만히 있으면 되는데 말이죠,,??? 

그래서 시작좌표를 1로 두었습니다.

---

다음은 코드입니다.

 

오늘은 심심해서 강제 옵셔널 할당 해제를 사용하지 않고

함수를 사용하고,

그냥 옵셔널 바인딩을 사용했습니다  (뭔가 어색하네요)

 

import Foundation
/**
 *
 *
 * 주의사항
 * 이전 코드에서는 map에서0 이 아닐경우 탐색을하는데,
 * 시작좌표가 0으로 표시되서 맨 마지막의 경우 이동하지 않아야 할게
 * 최소 2번 이동으로 출력되는데 ( 마지막 input 답과 다름)
 * 이거만 주의하면 된다
 *  그래서 시작좌표를 1로하고 반환을 mpa[좌표] - 1 로 했다.
 */

solution()

/**
 * res == 값 저장
 * testCase 옵셔널 바인딩으로 값 받음
 * coord에 시작점, 도착점 저장 ( inputSeq함수를 통해 값 대입)
 * length에 체스판 크기 저장
 * map에 원하는 도착지점까지 bfs탐색할 때 방문했는지를 표시함(0이면 탐색 x)
 * BFS탐색을 통해 값 도출
 */
func solution(){
    var res = ""
    let testCase : Int = inputData()
    for _ in 0..<testCase{
        
        var coord = [(Int,Int)]()
        let length = inputData()
        var map = Array(repeating: [Int](), count: length)
        for i in 0..<length{
            map[i] = Array(repeating: 0, count: length)
        }
        for _ in 0..<2{
            inputSeq(array: &coord)
        }
        res += "\(BFS(map: &map, array: coord))\n"
    }
    print(res)
}
/**
 * direction = 나이트가 이동할 수 있는 곳 물론 현재 나이트의 위치에서 이 값을 더해야 이동할 값이나옴
 * start X, Y 처음 나이트가 위치한 좌표
 * destination X, Y 도착 좌표
 * index == queue를 훑는데 사용 . dequeue할때 시간이 오래 걸릴까봐 index를 통해 탐색함
 */
func BFS(map : inout [[Int]], array: [(Int,Int)]) -> Int{
    let direction = [(2,1),(1,2),(-2,1),(-1,2),(2,-1),(1,-2),(-2,-1),(-1,-2)]
    
    let startX = array[0].0
    let startY = array[0].1
    let destinationX = array[1].0
    let destinationY = array[1].1

    var index = 0
    //맨 위의 주의사항으로 인해
    map[startY][startX] = 1
    var queue = [(startX,startY)]
    
    while(queue.count != index){
        
        for (dx,dy) in direction{
            let x = queue[index].0
            let y = queue[index].1
            let nx = x + dx
            let ny = y + dy
            
            if nx < 0 || nx > map.count - 1 || ny < 0 || ny > map.count - 1 {
                continue
            }
            //방문 x 이면
            if map[ny][nx] == 0 {
                //현재 좌표 x,y에서 나이트가 nx, ny로 이동함을 +1 로 표시
                map[ny][nx] = map[y][x] + 1
                //그 후 큐에 추가
                queue.append((nx,ny))
            }
            //도착했는가?
            if nx == destinationX && ny == destinationY{
                return map[ny][nx] - 1
            }
            
        }
        index += 1
    }
    return 0
}
func inputData() -> Int{
    if let input = readLine(){
        return Int(input) ?? 0
    }
    return 0
}

/*
 * 0 0 이 값이 readLine()을 통해 input에 저장될 때
 * 옵셔널 바인딩할때 input을 split한 다음에 input[0] input[1]로 쓸 수 없음
 * let 변수이기때문에, 그래서 var 타입의 변수를 통해 그 변수를 split결과로 대입해야함.
 */
func inputSeq(array: inout [(Int,Int)]) {
    if let input = readLine(){
        var seq = input.split(separator: " ").map{Int($0)}
        array.append((Int(seq[0] ?? -1), Int(seq[1] ?? -1)))
    
    }
}

 

질문은 환영입니다!!! 

 

긴 글 읽어주셔서 감사합니다