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

🥈 Silver2

 

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

 

✅ 정답풀이

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs(start_x, start_y, end_x, end_y, length):
    queue = deque([(start_x, start_y)])  
    visited = [[-1] * length for _ in range(length)]  # 모든 값을 -1로 초기화
    visited[start_x][start_y] = 0  # 시작 지점의 이동 거리 0으로 설정

    while queue:
        cx, cy = queue.popleft()

        if cx == end_x and cy == end_y:  # 도착 지점에 도달했을 때
            return visited[cx][cy]

        for i in range(8):
            nx, ny = dx[i] + cx, dy[i] + cy
            if 0 <= nx < length and 0 <= ny < length and visited[nx][ny] == -1:
                visited[nx][ny] = visited[cx][cy] + 1  # 이동 거리를 갱신
                queue.append((nx, ny))

    return -1  # 도착 지점에 도달할 수 없는 경우

n = int(input())
for _ in range(n):
    length = int(input())
    start_x, start_y = map(int, input().rstrip().split())  # 출발 지점
    end_x, end_y = map(int, input().rstrip().split())  # 도착 지점

    result = bfs(start_x, start_y, end_x, end_y, length)
    print(result)

visited 리스트에 이동한 거리를 저장하는 경우

 

✅ 정답풀이

import sys
from collections import deque

input = sys.stdin.readline

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


def bfs(start_x, start_y, end_x, end_y, length):
    queue = deque([(start_x, start_y, 0)])  # 큐에 이동 횟수도 함께 저장
    visited = [[0] * (length + 1) for _ in range(length + 1)]
    visited[start_x][start_y] = 1

    while queue:
        cx, cy, count = queue.popleft()

        if cx == end_x and cy == end_y:  # 도착지점에 도달했을 때
            return count

        for i in range(8):
            nx, ny = dx[i] + cx, dy[i] + cy
            if 0 <= nx < length and 0 <= ny < length and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx, ny, count + 1))

    return -1  # 도착지점에 도달할 수 없는 경우


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

    result = bfs(start_x, start_y, end_x, end_y, length)
    print(result)

메모리	시간
98880KB	2152ms

 

큐의 데이터 튜플에 이동한 거리를 저장하는 경우

 

 

문제를 처음보고 겁먹었지만 

오늘 풀었던 문제들을 잘 조합해보면서 풀다보니 무사히 해결될 수 있었다.

 

먼저 8방향으로 이동할 수 경우를 dx,dy값을 배열로 정의해주고, 각 n개의 테스트 케이스가 있기때문에 그에 해당하는 visited 리스트도 각각 생성해야하므로 dfs함수내에서 생성을 해주었다. 이게 처음 오답의 원인이였다..

 

이 문제도 주어지는 출발지점에서 도착지점까지의 이동횟수를 구하는것이기 때문에 최단거리를 구하는 방식으로 BFS로 풀이하였다.

visited배열에서 0과1로 방문여부를 구분하고, 큐에 현재좌표(nx,ny)와 이동거리 count값을 튜플로 관리하였다. 

이런 이동하는 문제에서 인덱스 유효성 검사는 꼭 필수이니 잊지말자...

 

 

큐에서 popleft로 꺼낸 원소가 현재 좌표(cx,cy)가 될것이고, 튜플로 함께 저장한 count를 리턴한다.

bfs에서 다음으로 순회할 노드를 살펴보기 위해 인접리스트를 확인하듯 8방향으로 이동할 수 있기 때문에 

nx,ny를 정의해서 각 방향마다 이동한 좌표를 구하고, 방문한적이 없다면 중복여부를 위한 방문처리와 count를 현재까지 이동한 visited[cx][cy]에 1을 더해 업데이트 해준다.

 

 

같이 풀어보면 좋을 문제

👉🏻 유기농 배추 1012번

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