[백준] 7562번 나이트의 이동 - 파이썬(Python)

시간 제한	메모리 제한
1 초	256 MB

문제 (링크)

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

7562번: 나이트의 이동

 

나의 풀이

from collections import deque

# 나이트의 8가지 이동
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [2, -2, 2, -2, 1, -1, 1, -1]

def bfs(start_x, start_y, target_x, target_y):
	q = deque()
    q.append((start_x, start_y))
    graph[start_x][start_y] = 1
    
    while q:
    	x, y = q.popleft()
        
        for i in range(8):
        	nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
            	if graph[nx][ny] == 0:
                	# 거리 계산을 위해 이전 값에서 + 1한 값을 저장해줌
                	graph[nx][ny] = graph[x][y] + 1
                    
                    # bfs 돌던 중 target x, y를 만나면 바로 리턴하여 종료해준 후 해당 위치의 거리값 리턴 
                    if nx == target_x and ny == target_y:
                    	return graph[nx][ny] - 1
                    
                    q.append((nx, ny))

# for문을 돌며 정답을 저장해줄 리스트

ans_list = []
t = int(input())

for _ in range(t):
	n = int(input())
    graph = [[0] * n for _ in range(n)]
    start_x, start_y = map(int, input().split())
    target_x, target_y = map(int, input().split())
    
    ans_list.append(bfs(start_x, start_y, target_x, target_y))

for x in ans_list:
	if x == None:
    	print(0)
	else: print(x)

 

접근 방법 및 코드 설명

전형적인 bfs 혹은 dfs를 사용하는 문제이다.

 

시작점에서 시작해, 미리 지정해둔 8가지의 이동방식대로 bfs를 수행하며, 각 위치를 방문할 때마다 이동 횟수를 저장하기 위해 이전 위치의 값 + 1을 현재 위치에 저장시켜주는 작업을 거쳤다.

 

그렇게 bfs로 방문을 하다가 목표 지점에 도달하면 다른 곳은 더 이상 방문할 필요가 없으므로 바로 리턴해주도록 함수를 작성했다.

 

또한, 시작점을 이미 방문처리하였다고 표시하기 위해 초기값을 1로 설정해놓았으므로, 마지막 리턴 값에선 목표 지점의 값에서 1을 뺀 수를 리턴해주었다.

 

 

이 문제에서 중요한 것은 bfs를 수행하다가 목표 위치를 만나면 함수를 종료시켜줘야 시간초과가 나지 않는다는 것이다.

 

처음에 그렇게 안짰다가 시간초과가 나서 원인을 모르고 bfs가 아닌 dfs만을 사용하도록 설계된 문제인가 했지만 다행히 그 문제는 아니었다.

 

이제 좀 bfs 문제에 대한 감이 잡히는 것 같은데, 이럴 때 일수록 좀 더 고차원적인 응용문제에 많이 도전해봐야겠다.