[그래프] Python - 7562번, 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

import sys
input = sys.stdin.readline


def getNextPos(x, y):
    global isVisited
    RET = []
    dx = [-1, -2, -2, -1, 1, 2, 2, 1]
    dy = [-2, -1, 1, 2, 2, 1, -1, -2]

    for i in range(8):
        curX, curY = x+dx[i], y+dy[i]
        if 0 <= curX <= I-1 and 0 <= curY <= I-1:
            if isVisited[curX][curY] == False and ((posEnd[X]-curX > 0 and dx[i] > 0) or (posEnd[X]-curX < 0 and dx[i] < 0) or (posEnd[X]-2 <= curX <= posEnd[X]+2)) and ((posEnd[Y]-curY > 0 and dy[i] > 0) or (posEnd[Y]-curY < 0 and dy[i] < 0) or (posEnd[Y]-2 <= curY <= posEnd[Y]+2)):
                RET.append([curX, curY])
                isVisited[curX][curY] = True
    return RET


X, Y = 0, 1
T = int(input())
for _ in range(T):
    I = int(input())
    posStart = list(map(int, input().split()))
    posEnd = list(map(int, input().split()))
    if posStart == posEnd:
        print(0)
        continue

    isVisited = [[False]*I for _ in range(I)]
    isVisited[posStart[X]][posStart[Y]] = True
    todo = getNextPos(posStart[X], posStart[Y])
    cntMove = 0
    while todo:
        cntMove += 1
        nextTodo = []
        for curPos in todo:
            if curPos == posEnd:
                nextTodo = []
                break
            nextTodo += getNextPos(curPos[X], curPos[Y])
        todo = nextTodo
    print(cntMove)

 

 

bfs를 해주면 된다.

다만 나는 isVisited로 중복 방문을 허용하지 않았으며, 또 지협적인 것처럼 보여도 매우 일반적인 조건을 달아서 시간 복잡도를 대폭 줄였다.

getNextPos()의 긴 if문에서

((posEnd[X]-curX > 0 and dx[i] > 0) or (posEnd[X]-curX < 0 and dx[i] < 0) or (posEnd[X]-2 <= curX <= posEnd[X]+2))

and

((posEnd[Y]-curY > 0 and dy[i] > 0) or (posEnd[Y]-curY < 0 and dy[i] < 0) or (posEnd[Y]-2 <= curY <= posEnd[Y]+2))

이 부분이 가장 중요하다.

 

우선 나는 해당 위치로 이동하는 것을 두 개의 옵션으로 나누었다.

1. 거리가 멀어서 일단 그 방향으로 간다. 2. 충분히 가까워지면 위치를 살짝씩 조절해서 목적지에 도착한다.

(posEnd[X]-curX > 0 and dx[i] > 0) or (posEnd[X]-curX < 0 and dx[i] < 0)가 의미하는 바는, 1번이다. 그림으로 설명하자면, 다음과 같다.

보라색이 목적지이다.

그 다음으로는, (posEnd[X]-2 <= curX <= posEnd[X]+2)가 있는데, 이는 예상했듯이 2번을 의미한다. 이것을 넣은 이유가 핵심인데, 2라는 숫자가 나오게 된 경위는, 어떤 위치에서 (1, 0), (2, 0), (1, 1)를 각각 이동한다고 했을 때, 최소한의 움직임으로 갈 때 그 움직임들의 범위가 +-2였기 때문이다.

 

시간 복잡도는 상위 1%이며, 압도적으로 빠른(60ms~100ms)와 평균 수준(1600ms~)의 어느 한 부분에 위치해있다.

지협적인 것 같으면서 모든 경우를 포괄하는 풀이를 스스로 생각해냈으며, 그 수준도 우수하므로 이에 큰 의의를 둔다.