[백준] 7562 : 나이트의 이동 (+ 그래프 정리)

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

7562번: 나이트의 이동

---

코드

from collections import deque

T = int(input()) # 테스트 케이스 개수

for _ in range(T):
    I = int(input()) # 체스판 한 변의 길이
    row_now, col_now = map(int, input().split()) # 현재 위치
    row_target, col_target = map(int, input().split()) # 타겟 위치
    row_rot = [-2, -1, 1, 2, 2, 1, -1, -2] # 나이트 이동 가능한 행 방향
    col_rot = [1, 2, 2, 1, -1, -2, -2, -1] # 나이트 이동 가능한 열 방향
    chess = [[0] * (I) for _ in range(I)]

    dq = deque([[row_now, col_now]])
    while dq:
        row_tmp, col_tmp = dq.popleft()
        if row_tmp == row_target and col_tmp == col_target:
            print(chess[row_target][col_target])
            break
        for k in range(8):
            row_move = row_tmp + row_rot[k]
            col_move = col_tmp + col_rot[k]
            if 0 <= row_move < I and 0 <= col_move < I and not chess[row_move][col_move]:
                chess[row_move][col_move] = chess[row_tmp][col_tmp] + 1
                dq.append([row_move, col_move])

풀이

 이전에 풀어보았던 최단 거리 bfs 유형과 상당히 비슷해서 손쉽게 풀이할 수 있었다. 알고리즘 문제를 유형화하며 풀어가니 문제 해법을 잡아갈 수 있는 것 같다. 특히 그래프 문제에서는 상하좌우 이동과 같은 방향 이동 문제가 자주 출제되는 것 같다고 느꼈다.

 해당 문제에선 1) 방향 인덱스 설정 및 for문 통한 방향 이동, 2) 최단 거리 -> bfs 이용, 3) 정지 조건, 4) 이동된 방향 인덱스 조건 확인 (범위 내 + 이미 방문한 인덱스인지 여부) 의 확인이 다른 문제와 동일하게 필요하다.

 이 문제와 별개로 그래프 유형 및 주의해야 할 점을 정리하며 해당 글을 마치고자 한다.

1) BFS
- 최단 거리(=최단 시간)의 경우 BFS 사용
- from collections import deque를 통해 덱 자료형 사용

2) DFS
- import sys, sys.setrecursionlimit을 이용해 최대 재귀 깊이 설정 (파이썬 기본 재귀 깊이가 매우 얕기 때문)

3) 인접 행렬, 인접 리스트
- 인접 행렬의 경우 입력 데이터에 크기에 맞는 모든 2차원 메모리 공간을 미리 생성해두어야 하기 때문에 입력이 큰 경우 메모리 제한으로 인한 에러가 발생할 수 있음
- 따라서 이러한 경우 인접 리스트를 활용하는 것이 효율적임

4) 인접 정점 방문 순서
- 주어진 문제에서 인접 정점 방문 순서를 오름차순으로 주었는지, 내림차순으로 주었는지 확인 후 입력받은 데이터 sorting

5) 방향 이동 출제 경향 ↑
- 일직선, 상하좌우, 2차원 n방향 이동 문제가 자주 출제
- 코드의 가독성 및 헷갈림 방지를 위해 row, col과 같은 명확한 변수 설정하기