백준 7562 - 파이썬

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

7562번: 나이트의 이동

문제 풀이

처음에 이 문제를 보고 완전 탐색을 통해 모든 경우의 수를 찾아보면 되겠다 싶었다. 하지만 이런 방법은 보통 시간 초과가 날 가능성이 높기에 좀더 효율적인 방법이 없나 싶었지만 찾지 못했고, 완전 탐색을 통해 구현을 해봤다.

 

import sys
from collections import deque
input = sys.stdin.readline

t = int(input())

for _ in range(t):
  n = int(input())
  x, y = map(int, input().split())
  sx, sy = map(int, input().split())

  matrix = [[0] * n for _ in range(n)]
  visited = [[False] * n for _ in range(n)]

  q = deque()

  moves = ((2, 1), (-2, 1), (-2, -1), (2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2))

  def bfs(x, y):
    q.append((x, y))
    visited[x][y] = True

    while q:
      x, y = q.popleft()

      if x == sx and y == sy:
        return 0

      for move in moves:
        nx = x + move[0]
        ny = y + move[1]

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

        if nx == sx and ny == sy:
          visited[nx][ny] = True
          return matrix[x][y]+1
          
        if visited[nx][ny] == False:
          q.append((nx, ny))
          visited[nx][ny] = True
          matrix[nx][ny] = matrix[x][y] + 1    

  answer = bfs(x, y)
  print(answer)

기존의 BFS와 차이점은 이동리스트를 나이트의 움직임에 맞춰 정의해 뒀다는 점이다. 나머지는 기존의 BFS와 유사하다.

 

이 문제를 풀면서 느낀 점은 이렇게 푸는 방법이 맞나 싶어도 구현 문제는 그 방법을 해보면서 최적화를 시키는게 더 효율적인거 같다는 생각이 든다.