[BOJ] 7562번 나이트의 이동 / 사용언어 : 파이썬(python)

※ 문제링크 

7562번: 나이트의 이동

해당문제는 BFS를 활용하여 풀 수 있는 문제로, deque를 활용하여 BFS를 구현하여 해결을 하였다. 체스의 나이트의 이동조건을 알고 있는 사람이라면 보다 쉽게 해결할 수 있는 문제로 방문한 위치를 기록하고 목표점에 도달했을때에 반복문을 종료하는 방식으로 해결할 수 있었다. 자세한 문제풀이와 코드는 아래와 같다.

1. 입력받은 값을 바탕으로 반복문을 작성하고, 체스판을 작성하여 출발점만 1로 표기해준다. 

2. 나이트의 최초위치와 목표점과 같을때에는 바로 0을 출력하고 그외의 경우에는 반복문을 돌려서 목표점이 나올때까지 반복한다.

3. 목표점이 나오면 반복문을 종료하고 카운트 값을 출력한다.

+ 시간 단축을 위해 sys함수를 사용하였으며, sys사용시에는 개행문자에 유의하여 입력 및 출력할 수 있도록 해야한다.

 

import sys
from collections import deque

def bfs(x, y):
    cp = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < T and 0 <= ny < T:
            if nx == x2 and ny == y2:
                cp += 1
                board[ny][nx] = 1
                break
            if board[ny][nx] == 0:
                board[ny][nx] = 1
                queue.append([nx, ny])
    return cp

# input = sys.stdin.readline

N = int(input()) # 반복문 횟수
for i in range(N):
    T = int(input())
    board = [[0 for _ in range(T)] for _ in range(T)]
    y1, x1 = map(int, input().split())
    board[y1][x1] = 1
    y2, x2 = map(int, input().split())

    if x1 == x2 and y1 == y2:
        if i == N-1:
            sys.stdout.write(f'{0}')
        else:
            sys.stdout.write(f'{0}\n')
    else:
        dx = [-2, -2, -1, -1, 1, 1, 2, 2]
        dy = [-1, 1, -2, 2, -2, 2, -1, 1]
        cnt = 0
        queue = deque()
        queue.append([x1, y1])

        while True:
            if x1 == x2 and y1 == y2:
                print(0)
            else:
                cnt += 1
                for _ in range(len(queue)):
                    x, y = queue.popleft()
                    check = bfs(x, y)
                    if check == 1:
                        break
                if check == 1:
                    break
        if i == N-1:
            sys.stdout.write(f'{cnt}')
        else:
            sys.stdout.write(f'{cnt}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.