7562. 나이트의 이동
문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문
접근 과정
- 우선 나이트의 이동에 대한 정의가 필요하다.
- 현재의 특정 좌표에서 나이트가 이동할 수 있는 경우의 수는 8가지이다.
- 나이트의 현재 위치를 큐에 넣고, 8방향으로 계속 이동시킨다.
- 체스판의 범위를 벗어나지 않는 선에서 나이트는 계속 이동하다 목표 지점에 도착한다.
- 방문처리는 필요할까?
- 다녀갔다는 표시를 남겨주지 않는다면 나이트는 무한히 이동할 것이다.
- 체스판의 범위 내에 있고, 방문하지 않았다면 체스판과 같은 사이즈의 visited 배열의 해당 좌표에 이동 횟수를 넣어준다.
- 체스판의 길이는 4부터 최대 300이고, 시간 제한은 1초이다.
풀이
# 기본 input() 입력으로 제출했을 때 시간초과가 발생했다!
# 큐를 deque로 변경하고, sys를 통해 입력을 받아오게 수정했음에도
# 시간이 꽤 오래 걸린 것을 보면 효율성에 큰 문제가 있었던 것으로 보인다.
# 효율성을 더 올릴 수 있는 방법을 생각해봐야겠다.
import sys
from collections import deque
dx = [-1, -2, -2, -1, 1, 2, 2, 1] # 한 위치에서 나이트가 이동할 수 있는 경우
dy = [-2, -1, 1, 2, -2, -1, 1, 2]
def BFS(x, y):
global ans
visited = [[0] * chess_length for _ in range(chess_length)]
Q = deque()
Q.append([x, y])
while Q:
x, y = Q.popleft()
for i in range(8):
tx, ty = x + dx[i], y + dy[i]
if 0 <= tx < chess_length and 0 <= ty < chess_length and not visited[tx][ty]:
Q.append([tx, ty])
visited[tx][ty] = visited[x][y] + 1
if tx == target_x and ty == target_y:
ans = min(ans, visited[tx][ty])
for test_case in range(int(sys.stdin.readline().rstrip())):
chess_length = int(sys.stdin.readline().rstrip())
chess_board = [[0] * chess_length for _ in range(chess_length)]
knight_x, knight_y = map(int, sys.stdin.readline().split())
target_x, target_y = map(int, sys.stdin.readline().split())
ans = 10e9
if knight_x == target_x and knight_y == target_y:
print(0) # 시작 지점과 목표 지점이 동일한 경우는 바로 0을 출력한다.
continue
BFS(knight_x, knight_y)
print(ans)
아직 많이 부족합니다ㅠㅠ
접근 방향이 조금 아쉬웠거나, 복잡도 계산이 잘못됬거나,
어쩌면 코드가 잘 이해되지 않으실 수 있어요!
댓글로 자유롭게 의견이나 가르침을 남겨주신다면
제가 더 성장하는데 큰 도움이 될거에요 :)
읽어주셔서 감사합니다!
Author And Source
이 문제에 관하여(7562. 나이트의 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@applevalley/7562.-나이트의-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)