[백준/파이썬][Silver I] 데스 나이트 - 16948

[Silver I] 데스 나이트 - 16948

문제 링크

성능 요약

메모리: 114540 KB, 시간: 132 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 3월 6일 21:29:13

문제 설명

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r₁, c₁), (r₂, c₂)가 주어진다. 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r₁, c₁, r₂, c₂가 주어진다.

출력

첫째 줄에 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

풀이

from collections import deque

di = [-2, -2, 0, 0, 2, 2]
dj = [-1, 1, -2, 2, -1, 1]

def is_valid(i, j, N) :
    return 0 <= i < N and 0 <= j < N

def bfs(si, sj, ei, ej, N) :
    visited = [[-1] * N for _ in range(N)]
    visited[si][sj] = 0
    q = deque()
    q.append((si, sj, 0))

    while q :
        ci, cj, cnt = q.popleft()
        if (ci, cj) == (ei, ej) :
            return cnt

        for d in range(6) :
            ni, nj = ci + di[d], cj + dj[d]

            if is_valid(ni, nj, N) and visited[ni][nj] == -1 :
                visited[ni][nj] = visited[ci][cj] + 1
                q.append((ni, nj, visited[ni][nj]))

    return -1

def sol_16948() :
    N = int(input())
    r1,c1,r2,c2 = map(int, input().split())

    print(bfs(r1, c1, r2, c2, N))

sol_16948()

1. BFS 를 이용할 거라 deque를 import 
2. di, dj 리스트를 미리 만들어 이동 방향과 거리를 미리 설정함. (본인은 이게 실수할 확률이 적어서 선호하는 편임)
3. is_valid : 체스판 위에 존재하는지에 대해서 묻는 함수, 원래는 선호하지 않았는데 한 번 시도해보았음.
4. bfs : BFS(si, sj, ei, ej) : si, sj : 시작좌표, ei, ej : 종료 좌표 
   1. visited 배열을 만들어서 -1 로 초기화
   2. visited[si][sj] 시작부분을 방문으로 시작 = 0 으로 초기화
   3. 큐(q)에 si, sj, 0(cnt) 를 추가함.
   4. while q : BFS 알고리즘 부분
      1. ci, cj, cnt : 현재 좌표와 cnt를 popleft함.
      2. if 현재좌표 = 종료좌표 : return cnt : 여기서 정답을 리턴함. 역시 실수를 줄이기 위함.
      3. 원래 체스의 나이트는 8방향이지만, 데스나이트는 6방향이므로 range(6)으로 설정
         next i, j (ni,nj) 구하고 is_vaild 함수와 visited[ni][nj] 방문 흔적이 없는지 확인
      4. 현재 방문 횟수를 +1 하여 갱신하고 큐에 ni, nj, visited[ni][nj]를 삽입하여 루프를 완성
      5. 만약 이 루프가 다 끝나더라도 결과가 나오지 않는다면, -1를 리턴
   5. main 함수(sol_16948): 변수를 받아오고 bfs에 넣어서 결과값을 프린트.

전형적인 BFS 문제였다. 관련된 문제를 오랜만에 풀어보니까 조금 헤맸던 부분도 있지만, 비교적 쉽게 해결할 수 있었다.