백준 7562(파이썬):나이트의 이동
백준 7562번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/7562
문제 내용
나의 풀이
import sys
from collections import deque
input=sys.stdin.readline
def bfs(start_x,start_y,end_x,end_y):
global minimum
queue=deque()
queue.append((start_x,start_y,0))
visited[start_x][start_y]=1
while queue:
x,y,count=queue.popleft()
for i in range(8):
rx,ry=x+dx[i],y+dy[i]
if 0<=rx<l and 0<=ry<l and visited[rx][ry]==0:
if rx==end_x and ry==end_y:
minimum=min(minimum,count+1)
else:
visited[rx][ry]=1
queue.append((rx,ry,count+1))
return print(minimum)
num=int(input())
dx=[-2,-2,2,2,-1,-1,1,1]
dy=[-1,1,-1,1,-2,2,-2,2]
for i in range(num):
l=int(input())
chess=[[0]*l for _ in range(l)]
visited=[[0]*l for _ in range(l)]
start_x,start_y=map(int,input().split())
end_x,end_y=map(int,input().split())
if start_x==end_x and start_y==end_y:
print(0)
continue
minimum=1e9
bfs(start_x,start_y,end_x,end_y)
- 출발 지점과 목표 지점이 쪽같을 때는 0을 출력하도록 설정했다.
- 이동해야 할 때는 BFS탐색으로 목표지점 도달시 최소값을 갱신해준 후 마지막에 출력해준다.
- 입력된 테스트 횟수만큼 반복 실행하도록 설정했다..
시간이 조금 오래 걸렸다…
풀이를 본 후
방문 노드를 만들지 않고 배열에 값을 더해가면서 진행했다. 아마 이 부분에서 시간차이가 발생한듯하다
내 풀이: 2436ms, 다른 풀이: 1336ms…
from collections import deque
import sys
input = sys.stdin.readline
t = int(input().rstrip())
def bfs() :
dx = [-1, 1, 2, 2, 1, -1, -2, -2]
dy = [2, 2, 1, -1, -2, -2, -1, 1]
q = deque()
q.append((startX, startY))
while q :
x, y = q.popleft()
if x == endX and y == endY :
return matrix[x][y] -1
for i in range(8) :
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<l and 0<=ny<l and matrix[nx][ny] == 0 :
matrix[nx][ny] = matrix[x][y] + 1
q.append((nx,ny))
for _ in range(t) :
l = int(input().rstrip())
startX, startY = map(int, input().rstrip().split())
endX, endY = map(int, input().rstrip().split())
matrix = [[0]*l for _ in range(l)]
matrix[startX][startY] = 1
print(bfs())
해결한 후
시간 초과가 발생하지 않도록 최선의 조건을 생각해봐야 할것같다….
