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

https://www.acmicpc.net/submit/7562/55594757

로그인

 

1. 내가 작성한 코드

기존 문제들은 dx, dy가 동, 서, 남, 북 네 방향으로만 이동할 수 있는데,

 

이 문제는 각기 다른 8개의 방향으로 이동할 수 있다는 점을 제외하면 

 

미로찾기와 동일한 문제이다.

 

from collections import deque

t = int(input()) #테스트 케이스 횟수

def bfs():

  #이동할 수 있는 좌표
  dx = [2,2,1,1,-2,-2,-1,-1]
  dy = [-1,1,-2,2,-1,1,-2,2]

  queue = deque()
  queue.append((start_x,start_y))
  maps[start_x][start_y]= 1

  while queue:
    x,y = queue.popleft()
    if x == end_x and y == end_y:
      print(maps[x][y]-1)
      return
    for i in range(8):
      nx = x+dx[i]
      ny = y+dy[i]

      if nx<0 or ny<0 or nx>=n or ny>=n:
        continue

      if maps[nx][ny] == 0:
        maps[nx][ny] = maps[x][y] + 1
        queue.append((nx,ny))

for _ in range(t):
  n = int(input()) #체스판 한 변의 길이
  maps = [[0]*n for _ in range(n)]
  start_x,start_y = map(int,input().split())
  end_x,end_y = map(int, input().split())
  bfs()

 

 

 

이제 실버 단계에 있는 dfs/bfs 는 약간 감을 잡은 것 같다

 

그래프 감 잡은 줄 알았는데 이번엔 DP 등장 ㅠㅠ 넘나리 어려운 것