문제
7562 나이트의 이동 문제를 풀었습니다.
-
알고리즘
-
BFS
-
이유 : 하나의 루트를 깊게 탐색하는게 중요한 게 아니라, 시작점에서 특정 루트로 가는 최단거리를 찾아내는 것이 중요한 문제이기 때문
-
특이사항 : 이동할 때마다의 count를 세어줘야하므로, queue에서 count를 함께 갖고 BFS를 돌아주어야 합니다.
-
-
난이도 : solved.ac 기준 실버2. 코딩테스트 기준으로는 굳이 나오지 않을 만한 쉬운 문제라고 생각한다. (BFS는 풀이시간이나 코드가 길다보니 2시간 이하의 코딩테스트+올솔컷 에서는 잘 나오지 않는 편인데, 만약 나온다면 해당 문제보단 조금 더 난이도 있게 나온다. solved.ac 기준 골드 4 정도로 나옴.)
풀이
import sys
sys.setrecursionlimit(10000)
from collections import deque
Dir = [[-1,2], [-2,1], [1,2], [2,1],
[-1,-2],[-2,-1],[1,-2],[2,-1]]
def isValid(N, x, y) :
return x>=0 and x<N and y>=0 and y<N
def bfs(N, MAP, x, y, targetX, targetY) :
if x == targetX and y == targetY : return 0
visited = [[False]*N for _ in range(N)]
queue = deque([])
queue.append((x,y,0))
visited[y][x] = True
while queue :
tempX, tempY, cnt = queue.popleft()
for d in Dir :
dx = tempX + d[0]
dy = tempY + d[1]
if isValid(N, dx, dy) and not visited[dy][dx] :
if dx == targetX and dy == targetY : return cnt+1
visited[dy][dx] = True
queue.append((dx,dy,cnt+1))
return 0
def _7562() :
T = int(input())
for _ in range(T) :
N = int(input()) # 한 변의 길이
MAP = [[0]*N for _ in range(N)]
x, y = map(int, input().split())
targetX, targetY = map(int, input().split())
cnt = bfs(N, MAP, x, y, targetX, targetY)
print(cnt)
return 0
_7562()
다른 사람의 코드에서 배워오기
- 파이썬은
0<=x and x<n
이 아니라(0<=x<n)
으로 묶어서 쓸 수 있다. (뭐 이런 언어가..)