[99클럽 코테 스터디 9일차 TIL] 나이트의 이동 - 백준 7562

오늘의 문제 키워드가 DFS/BFS였지만 이번에는 명확하게 BFS를 활용하는 문제였다.

 

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

체스판 위에 한 나이트가 놓여져 있다. 
나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 
나이트가 이동하려고 하는 칸이 주어진다. 
나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[입력]
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 
첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 
체스판의 크기는 l × l이다. 
체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 
둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

풀이 접근

입력을 받아보자.

(0..<Int(readLine()!)!).forEach { _ in
    let i = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map { Int("\($0)")! }
    let end = readLine()!.split(separator: " ").map { Int("\($0)")! }

 

나이트가 움직일 수 있는 경우를 미리 저장해둔다.

let movable: [(Int, Int)] = [
    (-2,-1), (-1,-2), (1,-2), (2,-1), (-2, 1), (-1, 2), (1, 2), (2, 1)
]

 

 

로직을 생각해보자.

나이트가 현재 이동할 수 있는 칸들을 Queue에 넣고

다시 Queue의 나이트들이 이동할 수 있는 모든 칸들을 Queue에 넣는 과정을 반복한다.

BFS를 위한 변수를 정의한다.

var q: [[Int]] = [[start[0], start[1]]]
// 이미 도착위치라면 바로 결과를 출력하고 넘어간다.
if start == end {
    print(0)
    return
}
var qp = 0

이미 방문했다면 다시 방문할 필요가 없고, 방문 당시의 count 값이 해당 칸에 도착하기 위한 최소 이동 횟수가 된다.

방문 확인을 위한 Cache 변수를 정의한다.

var cache: [Int:Int] = [start[0] * i + start[1]:0]

BFS가 돌아갈 준비가 다 되었다.

    while qp < q.count {
        let p = q[qp]
        let count = cache[p[0] * i + p[1]]!
        qp += 1
        for m in movable {
            // 나이트가 이동한 좌표
            let n = [m.0 + p[0], m.1 + p[1]]
            
            // 체스판을 넘어간다면 확인할 필요 X
            if 0 > n[0] || n[0] >= i || 0 > n[1] || n[1] >= i {
                continue
            }
            
            // 도착했다면 결과값 출력 후 종료
            if n == end {
                print(count + 1)
                return
            }
            
            // 방문한 적이 없다면 방문 유무와 이동 횟수를 동시에 저장
            let key = n[0] * i + n[1]
            if cache[key] == nil {
                q.append(n)
                cache[key] = count + 1
            }
        }
    }

최종 코드 - Swift

(0..<Int(readLine()!)!).forEach { _ in
    let i = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map { Int("\($0)")! }
    let end = readLine()!.split(separator: " ").map { Int("\($0)")! }
    let movable: [(Int, Int)] = [
        (-2,-1), (-1,-2), (1,-2), (2,-1), (-2, 1), (-1, 2), (1, 2), (2, 1)
    ]
    var cache: [Int:Int] = [start[0] * i + start[1]:0]
    var q: [[Int]] = [[start[0], start[1]]]
    if start == end {
        print(0)
        return
    }
    var qp = 0
    while qp < q.count {
        let p = q[qp]
        let count = cache[p[0] * i + p[1]]!
        qp += 1
        for m in movable {
            let n = [m.0 + p[0], m.1 + p[1]]
            if 0 > n[0] || n[0] >= i || 0 > n[1] || n[1] >= i {
                continue
            }
            if n == end {
                print(count + 1)
                return
            }
            let key = n[0] * i + n[1]
            if cache[key] == nil {
                q.append(n)
                cache[key] = count + 1
            }
        }
    }
}

최종 코드 - Python3

Swift와 동일한 로직이다.

for _ in range(int(input())):
  i = int(input())
  start = list(map(int,input().split()))
  end = list(map(int,input().split()))
  if start == end:
    print(0)
    continue
  movable = [
    [-2,-1], [-1,-2], [1,-2], [2,-1], [-2, 1], [-1, 2], [1, 2], [2, 1]
  ]
  cache = {start[0] * i + start[1]:0}
  q = [[start[0],start[1]]]
  qp = 0
  while qp < len(q):
    p = q[qp]
    count = cache[p[0] * i + p[1]]
    qp += 1
    for m in movable:
      n = [m[0]+ p[0], m[1] + p[1]]
      if 0 > n[0] or n[0] >= i or 0 > n[1] or n[1] >= i:
        continue
      if n == end:
        print(count + 1)
        qp = len(q)
        break
      key = n[0] * i + n[1]
      if not key in cache:
        q.append(n)
        cache[key] = count + 1

Conclusion

처음에는 Dictionary의 키를 "\(n[0])\(n[1])"과 같이 문자열로 저장했더니 시간초과 문제가 생겼다.

앞으로도 키는 되도록 정수형으로 사용하자.