[2023 알고리즘 스터디] 4조 변준형 4주차 - 백준 7562

BFS(Breadth First Search, 너비우선탐색)

• 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 탐색을 할 때 너비를 우선으로 탐색. 즉 가까운 것 위주로 탐색한다. 이러한 특징때문에 최단경로를 찾는 문제에서 주로 사용.
• 자료구조 큐(Queue)를 사용함.

문제링크

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

7562번: 나이트의 이동

문제설명

• 나이트가 이동 가능한 좌표를 dx, dy의 형태로 만들어줍니다.
• 이동할 때 마다 방문 횟수에 1을 더합니다.(이동 횟수 기록)
• bfs 알고리즘을 이용.

소스코드

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

T = int(input().rstrip())
for _ in range(T):
    l = int(input().rstrip())
    start_x, start_y = map(int,input().rsplit())
    end_x, end_y = map(int,input().rsplit())
    visited = [[0] * l for _ in range(l)]
    visited[start_x][start_y] = 1

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

    queue = deque()
    queue.append((start_x,start_y,0))

    while(queue):
        temp = queue.popleft()
        x, y = temp[0],temp[1]

        if x == end_x and y == end_y:
            print(temp[2])
            break
        
        for i in range(8):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < l and 0 <= ny < l and visited[nx][ny]==0:
                visited[nx][ny] = 1
                queue.append((nx,ny,temp[2]+1))