[백준] 7562번: 나이트의 이동

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

INITIAL

I initially thought there was a mathematical way to find out the shortest path to destination like https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-1459%EB%B2%88-%EA%B1%B7%EA%B8%B0

but I was wrong. It is a textbook BFS question but I struggled way harder than I thought

solution

So we are essentially marking the depth of traversal. Before BFS, we initialise 2d count list of value -1. Notice i initialised as -1 becos i want the starting grid as value 0 because at starting point, it is move 0. I want to get the exact answer (without subtracting or adding 1) once i reach end point. At starting point, we make value 0 and traverse with knight moves (8 directions). If next move is within boundary and if we have not visited that grid before (i.e. count[next_x][next_y]==-1), then we increment that grid by current count +1. So we are spreading out our BFS traversal and incrementing and marking the depth. Once we reach the end index, we are guaranteed that it is the shortest path (depth) to reach that point so we return value of that end index.

confused

I initially placed the end condition outside like

 while queue:
            cur_x,cur_y= queue.popleft()
            for move in moves:
                next_x = move[0]+cur_x
                next_y = move[1]+cur_y
                if next_x==end_x and next_y==end_y:
                    return count[cur_x][cur_y]+1

It would work* except for edge cases like the starting and end point is the same. We will get a overvalued answer instead of 0 because we go to next_x,next_y (2,1) then after another bfs traversal, we traverse back to (0,0) when move is (-2,-1). So we get answer =2, which is wrong.

What we want to do is to return immediately when our current point is the end point.

correct:

import sys
input = sys.stdin.readline
from collections import deque

t= int(input())
for _ in range(t):
    n=int(input())
    start_x,start_y = map(int,input().split())
    end_x,end_y = map(int,input().split())

    moves = [[1,2],[2,1],[1,-2],[-1,2],[-1,-2],[2,-1],[-2,1],[-2,-1]]
    count = [[-1 for _ in range (n)] for _ in range(n)]
    def bfs():
        queue =deque()
        queue.append((start_x,start_y))
        # count = [[0 for _ in range (n)] for _ in range(n)]
        count[start_x][start_y]=0
        while queue:
            cur_x,cur_y= queue.popleft()
            if cur_x==end_x and cur_y==end_y:
                return count[cur_x][cur_y]
            for move in moves:
                next_x = move[0]+cur_x
                next_y = move[1]+cur_y

                if 0<=next_x<n and 0<=next_y<n and count[next_x][next_y]==-1:
                    count[next_x][next_y]= count[cur_x][cur_y]+1
                    queue.append((next_x,next_y))
    # print(count)
    val = bfs()
    print(val)

another more eff solution (to handle edge case)

when we get that edge case, we decrement the test count (tc) and run for the rest of the test cases. Usage of while loop is insightful whilst the implementation logic is same.

from collections import deque

dx = [1, 1, 2, 2, -1, -1, -2, -2]
dy = [2, -2, 1, -1, 2, -2, 1, -1]

def bfs(x, y, x_end, y_end):
    q = deque()
    q.append([x, y])
    a[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == x_end and y == y_end:
            return a[x][y]-1
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l:
                if a[nx][ny] == 0:
                    q.append([nx, ny])
                    a[nx][ny] = a[x][y] + 1

tc = int(input())
while tc:
    l = int(input())
    a = [[0]*l for _ in range(l)]
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    if x1 == x2 and y1 == y2:
        print(0)
        tc -= 1
        continue
    ans = bfs(x1, y1, x2, y2)
    print(ans)
    tc -= 1

complexity

The code you provided is for finding the minimum number of moves required for a knight on a chessboard to reach a specific destination square. The time and space complexity of the code is as follows:

Time Complexity:

• The code uses Breadth-First Search (BFS) to explore the possible moves of the knight on the chessboard. In the worst case, the knight may need to explore all possible squares on the n x n chessboard.
• The number of squares on the chessboard is n x n, so the worst-case time complexity of BFS in this context is O(n^2).

Space Complexity:

• The code uses a 2D count array of size n x n to keep track of the minimum number of moves required to reach each square on the chessboard.
• It uses a queue to perform BFS, and the queue can hold at most n x n elements in the worst case.
• Therefore, the space complexity is O(n^2) for the count array and O(n^2) for the queue, resulting in a total space complexity of O(n^2).

In summary, the time complexity of the code is O(n^2), and the space complexity is also O(n^2) due to the use of the 2D count array and the queue.