[백준] 7562 나이트의 이동

09 Apr 2021

문제

알고리즘
- BFS
- 이유 : 하나의 루트를 깊게 탐색하는게 중요한 게 아니라, 시작점에서 특정 루트로 가는 최단거리를 찾아내는 것이 중요한 문제이기 때문
- 특이사항 : 이동할 때마다의 count를 세어줘야하므로, queue에서 count를 함께 갖고 BFS를 돌아주어야 합니다.
난이도 : solved.ac 기준 실버2. 코딩테스트 기준으로는 굳이 나오지 않을 만한 쉬운 문제라고 생각한다. (BFS는 풀이시간이나 코드가 길다보니 2시간 이하의 코딩테스트+올솔컷 에서는 잘 나오지 않는 편인데, 만약 나온다면 해당 문제보단 조금 더 난이도 있게 나온다. solved.ac 기준 골드 4 정도로 나옴.)

풀이

import sys
sys.setrecursionlimit(10000)
from collections import deque 

Dir = [[-1,2], [-2,1], [1,2], [2,1],
[-1,-2],[-2,-1],[1,-2],[2,-1]]

def isValid(N, x, y) :
  return x>=0 and x<N and y>=0 and y<N

def bfs(N, MAP, x, y, targetX, targetY) :
  if x == targetX and y == targetY : return 0
  visited = [[False]*N for _ in range(N)]
  queue = deque([])
  queue.append((x,y,0))
  visited[y][x] = True

  while queue :
    tempX, tempY, cnt = queue.popleft()
    for d in Dir :
      dx = tempX + d[0]
      dy = tempY + d[1]
      if isValid(N, dx, dy) and not visited[dy][dx] :
        if dx == targetX and dy == targetY : return cnt+1
        visited[dy][dx] = True
        queue.append((dx,dy,cnt+1))
  
  return 0

def _7562() :
  T = int(input())
  for _ in range(T) :
    N = int(input()) # 한 변의 길이
    MAP = [[0]*N for _ in range(N)]
    x, y = map(int, input().split())
    targetX, targetY = map(int, input().split())
    cnt = bfs(N, MAP, x, y, targetX, targetY)
    print(cnt)
  

  return 0

_7562()

다른 사람의 코드에서 배워오기

파이썬은 0<=x and x<n이 아니라 (0<=x<n)으로 묶어서 쓸 수 있다. (뭐 이런 언어가..)