문제

문제 링크

---

풀이

정답 코드

bfs로 풀 수 있는 문제다.
나이트가 이동할 수 있는 8방향을 설정하고 이동 후 좌표가 처음 이동하는 좌표일 때 이전 좌표값 + 1을 해주면 된다.
동시에 조건문을 사용하여 목표지점에 도달했을 시 bfs를 종료하도록 설정했다.

from collections import deque

def bfs(graph, start, end):
    move = [(1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)]
    q = deque([start])
    while q:
        x, y = q.popleft()
        
        if (x, y) == end:
            return graph[y][x]
        
        for i in range(8):
            nx = x + move[i][0]
            ny = y + move[i][1]
            
            if 0 <= nx < l and 0 <= ny < l and graph[ny][nx] == 0:    
                graph[ny][nx] = graph[y][x] + 1
                q.append((nx, ny))

for i in range(int(input())): # number of test cases
    l = int(input()) # length
    start_x, start_y = map(int, input().split()) # start point
    end_x, end_y = map(int, input().split()) # end point
    
    board = [[0 for _ in range(l)] for _ in range(l)]
    print(bfs(board, (start_x, start_y), (end_x, end_y)))

---

문제점 - 시간 초과

문제 풀이 과정에서 어려움이 있던 부분은 속도였다.
초기에는 다음과 같은 코드를 사용했는데 시간 초과가 계속 났다.

# (다른 부분 생략)

if nx in range(l) and ny in range(l) and graph[ny][nx] == 0:
	graph[ny][nx] = graph[y][x] + 1
    q.append((nx, ny))

in range(l)로 해당 인덱스가 유효한 인덱스인지 판별하는 부분이 문제였던 것 같다. 단순 대소 비교는 두번의 작업을 수행하면 되지만 in range()를 이용할 경우 l이 커짐에 따라 수행해야 할 작업 횟수가 늘어난다고 생각했다.

확실히 차이가 있었다.

---

후기

로직뿐만 아니라 시간이나 메모리에도 신경을 써야 한다는 점을 다시 한번 느낀 문제였다.

파이썬에서의 실행 시간 절약 방법에 대해서 잘 정리된 다음 글을 발견했다. 참고해보면 좋을 것 같다.

https://camel-it.tistory.com/140