[문제풀이 py] B16948 데스나이트

데스나이트 / BFS 🍥

---

  🎠. 'queue'를 이용해서 'BFS'를 구현할 줄 알아야 한다 => 'queue = deque()'
  🎠. queue의 'depth(?)'를 구할 줄 알아야 한다. => 'leng = len(queue)', 'for in 문'

  from collections import deque
  N = int(input())
  cur_x, cur_y, target_x, target_y = list(map(int, input().split()))

  dx = [-2, -2, 0, 0, 2, 2]
  dy = [-1, 1, -2, 2, -1, 1]

  # arr2d = [[0]* N] * N
  # visited = [[False]* N] * N

  arr2d = [[0] * N for _ in range(N)]
  visited = [[False] * N for _ in range(N)]

  flag = 0
  def bfs(x, y):
      global flag
      queue = deque()
      queue.append([x, y])
      visited[x][y] = True
      cnt = 0
      while queue:
          leng = len(queue)
          for _ in range(leng):
              cur = queue.popleft()
              if target_x == cur[0] and target_y == cur[1]:
                  flag = 1
                  print(cnt)
                  return
              for i in range(6):
                  nx = cur[0] + dx[i]
                  ny = cur[1] + dy[i]
                  # print("nx:", nx, "ny:", ny)
                  if nx < 0 or ny < 0 or nx >= N or ny >= N:
                      continue
                  if not visited[nx][ny]:
                      visited[nx][ny] = True
                      queue.append([nx, ny])
          cnt += 1

  bfs(cur_x, cur_y)
  # print("flag:", flag)
  if flag == 0:
      print(-1)

💡. 문제 접근 방법
: 출발지에서 목적지까지 최소 이동 횟수를 구하라는 말에서 BFS를 생각했다.
queue를 이용해서 쉽게 구현할 수 있었다.

🤡. 실수한 부분
: 범위를 벗어나는 부분에 대한 처리는 해줬지만,
이미 방문한 칸에 대한 조건문 처리를 해주지 않아 잠시 헤맸다.