Algorithm/Baekjoon

[Baekjoon, Python] 7562번 : 나이트의 이동

JMcunst 2021. 3. 14. 15:43
728x90
반응형

도입

백준 단계별 풀기 DFS와 BFS 아홉 번째 문제이다.

 

백준 7562번 문제, 입력, 출력

백준 7562번 입출력 예제 1

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

풀이

1. 숨바꼭질 문제와 유사하다. 숨바꼭질 문제의 경우 x축의 값들만 사용하였는데, 나이트의 이동은 좀 더 나아가 좌표를 사용한다는 점이다. BFS로 푼다. 나이트의 이동 가지수는 총 8가지이다. 따라서, dx, dy 좌표를 설정해서 8가지의 좌표를 만들어 준다. 

 

2. for문을 돌면서, 2차원 배열(체스판:mat_field)에 값들을 업데이트 하는 방식으로 BFS를 돌린다. BFS가 끝나면 다음과 같이 mat_filed가 완성되어 있을 것이다. 여기서 타겟 좌표의 값에서 1을 더해서 출력한다. mat_field[var_tx][var_ty] +1

입출력 예제 1, 1번째 mat_field

코드

from sys import stdin
from collections import deque

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

def bfs(var_x,var_y,var_tx,var_ty):
    queue = deque()
    queue.append([var_x,var_y])
    mat_field[var_x][var_y] = 1
    while(queue):
        var_nx, var_ny = queue.popleft()            # deque 왼쪽 값 읽고 삭제
        if var_tx == var_nx and var_ty == var_ny:
            print(mat_field[var_tx][var_ty]-1)
            break
        
        for i in range(8):
            nx = var_nx + dx[i]
            ny = var_ny + dy[i]
            if 0 <= nx < var_N and 0 <= ny < var_N and mat_field[nx][ny] == 0:
                queue.append([nx,ny])
                mat_field[nx][ny] = mat_field[var_nx][var_ny] + 1

var_T = int(stdin.readline())

for _ in range(var_T):
    var_N = int(stdin.readline())
    var_x,var_y = map(int, stdin.readline().split())
    var_tx,var_ty = map(int, stdin.readline().split())
    mat_field = [[0] * var_N for i in range(var_N)]
    bfs(var_x,var_y,var_tx,var_ty)

마무리

dx, dy를 활용한 재밋는 문제였다.

728x90
반응형