7562번 - 나이트의 이동

💡 주어지는 예시 말고, 반례를 고민하는 습관을 들이자.

💡 특정 조건에 의해 탈출할 경우 잘 고민해보자

import sys
from collections import deque 

def bfs(curr_x, curr_y, target_x, target_y):
    
    dq = deque()
    dq.append((curr_x, curr_y))
    
    # 나이트 이동방향
    dx = [-2, -1, 1, 2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1 , -1, -2, -2, -1]

    while dq:
        x, y = dq.popleft()
        for idx in range(8):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            if nx == target_x and ny == target_y:
                return graph[y][x]
            
            if 0 <= nx < I and 0 <= ny < I and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                dq.append((nx,ny))

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    
    I = int(input())
    graph = [[0] * I for _ in range(I)]
    
    curr_x, curr_y = map(int,input().split(' '))
    graph[curr_y][curr_x] = 1
    
    target_x, target_y = map(int,input().split(' '))
    graph[target_y][target_x] = 2
    
    if curr_x == target_x and curr_y == target_y:
        print(0)
        continue
    
    print(bfs(curr_x,curr_y,target_x,target_y))

• 위 문제도 일반적인 bfs 문제와 동일하였지만, 기존 상하좌우와는 다르게 나이트의 이동방향에 맞춰서 이동하는 문제였다. (나이트는 가로 2칸, 세로 1칸을 움직일 수 있다.)
• 결론적으로 시작점과 목적점까지 최소 얼마나 움직였는지를 갈 수 있냐 이기떄문에, BFS를 사용하였고, 이동할 때마다 graph의 값을 +1 시켜주면서 visited 배열도 생략해주고, 목적점까지의 경로도 구할 수 있었다.
• 추가적으로 입력받은 시작점과 목적점을 bfs()에 추가하여 넣어주어, 처음부터 dq에 시작점을 넣고, 탈출 조건으로 목적점을 넣어서 풀이하였다.

💡 오답 해결

for _ in range(T):
    
    I = int(input())
    graph = [[0] * I for _ in range(I)]
    
    curr_x, curr_y = map(int,input().split(' '))
    graph[curr_y][curr_x] = 1
    
    target_x, target_y = map(int,input().split(' '))
    graph[target_y][target_x] = 2
    
    if curr_x == target_x and curr_y == target_y:
        print(0)
        break
    
    print(bfs(curr_x,curr_y,target_x,target_y))

• 처음에는 가장 위에 보이는 예제 입출력값에만 집중하여, 시작점과 목적점이 동시에 들어오면 0을 출력하고 종료해주는 방식을 선언했다.
• 하지만 이는 시작점과 목적점이 동일한 경우가 가장 마지막에 나올때만 성립이 되어 자꾸 16퍼에서 오답이 발생하였다.
• 따라서 해당 경우가 나와도 0을 출력해주고 다음 테스트 케이스를 받아야하기 떄문에 break 에서 continue로 변경해서 정답을 맞추었다.