[Python][백준/BOJ] 7562번 : 나이트의 이동

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

7562번: 나이트의 이동

 

내 코드

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

move = [(2,1),(1,2),(2,-1),(1,-2),(-1,2),(-2,1),(-2,-1),(-1,-2)]
t = int(input())

def bfs(x, y):
    q = deque()
    q.append((x,y))
    while q:
        x, y = q.popleft()
        if ex == x and ey == y:
            return board[ex][ey]-1
        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if 0<= nx <size and 0<= ny < size and not board[nx][ny]:
                q.append((nx,ny))
                board[nx][ny] = board[x][y]+1
                
    

for _ in range(t): #테스트
    size = int(input())
    board=[[0]*size for _ in range(size)] #체스판
    x, y = map(int, input().split())
    board[x][y]=1
    ex, ey = map(int, input().split())
    print(bfs(x,y))

 

BFS, 코드리뷰

해당 문제는 완벽한 BFS 문제다. 실버 2가 아니라 실버 1인 이유는, 아무래도 이동하는 범위가 늘어나서 그런 것이 아닐까 싶다.

나이트의 이동 범위

상하좌우만 있는 것들이 대부분인데, 난이도가 높아지면 높아질수록 이동할 수 있는 방향이 늘어난다. 하지만 이를 해결하는 방법은 정말 간단하다. 

원점을 기준으로 하고 이동할 수 있는 범위를 (1,2), (2,1) 이렇게 좌표만 찍어놓으면 된다. 그러면 코드 안에서 알아서 움직인다.

 

move = [(2,1),(1,2),(2,-1),(1,-2),(-1,2),(-2,1),(-2,-1),(-1,-2)]

이처럼 나는 아예 (x, y) 꼴로 좌표를 모두 저장해놓았다.

for _ in range(t): #테스트
    size = int(input())
    board=[[0]*size for _ in range(size)] #체스판
    x, y = map(int, input().split())
    board[x][y]=1
    ex, ey = map(int, input().split())
    print(bfs(x,y))

그리고 이것은 main함수인데, 기본적인 구현을 해주었다.

테스트 케이스가 여러개라서 초기화해야 할 사항들이 많다.

• size 초기화
• board[size][size] 초기화
• 시작점 x, y 초기화
• 끝점 ex, ey 초기화

 

def bfs(x, y):
    q = deque()
    q.append((x,y))
    while q:
        x, y = q.popleft()
        if ex == x and ey == y:
            return board[ex][ey]-1
        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if 0<= nx <size and 0<= ny < size and not board[nx][ny]:
                q.append((nx,ny))
                board[nx][ny] = board[x][y]+1

BFS 함수는 여느 BFS와 다를 것 없다. 특히 move 함수는 (x, y) 형태로 되어 있기 때문에 x와 y를 처리할 때는 for dx, dy in move로 두 개를 불러내는 것이 좋다.

 

BFS는 보통 최소 거리를 찾아내는 문제에 자주 사용되기 때문에 이렇게 생각하면 편하다.

1. 현재 원점이 (x, y)일 때 board[x][y] = 1 해주기 (방문했다는 의미)
2. 지금부터 ex, ey까지 갈건데, 만약 x, y가 ex, ey가 되면 그 수에 -1(이동한 거리니까)을 해준 값을 반환하기
3. 맵 안에 있으면서 방문하지 않았다면 그 전까지 이동한 값에+1 해주기

그리고 추가로 bfs는 while q가 세트라는 것을 기억하기!

while q 를 하기 위해서는 q에 뭔가가 들어있어야 하니까  q.append(x, y) 해주고 while q 하고 x, y = q.popleft() 하기