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

문제 링크 : https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 :

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 : 

5
28
0

 

코드

from collections import deque

def bfs(start, goal, visited, c_size, result):
    dx = [-1, -2, -2, -1, 1, 2, 2, 1]
    dy = [2, 1, -1, -2, -2, -1, 1, 2]

    queue = deque([start])
    visited[start[0]][start[1]] = 1

    while queue:
        v = queue.popleft()
        if v == goal:
            result.append(visited[v[0]][v[1]]-1)
            break
        for i in range(8):
            if 0 <= v[0]+dy[i] < c_size and 0 <= v[1]+dx[i] < c_size and visited[v[0]+dy[i]][v[1]+dx[i]] == 0:
                queue.append([v[0]+dy[i], v[1]+dx[i]])
                visited[v[0]+dy[i]][v[1]+dx[i]] = visited[v[0]][v[1]] + 1

test_num = int(input())
chess_size = []
result = []

for t in range(test_num):
    chess_size.append(int(input()))
    sx, sy = map(int, input().split())
    gx, gy = map(int, input().split())
    start = [sx, sy]
    goal = [gx, gy]
    visited = [[0]*chess_size[t] for _ in range(chess_size[t])]
    bfs(start, goal, visited, chess_size[t], result)

for r in range(test_num):
    print(result[r])

 

+ 기억해두기

 

map 사용해서 좌표 split하기!

 

그냥 split을 사용해도 되지만

그렇게 하게 되면

정수가 아니라 문자 형태로 들어가게 된다.

 

이럴 때 map 사용하면 간편!

sx, sy = map(int, input().split())

변수1, 변수2 = map(int, input().split())
변수1, 변수2 = map(int, input().split('기준문자열'))
변수1, 변수2 = map(int, input('문자열').split())
변수1, 변수2 = map(int, input('문자열').split('기준문자열'))

 

위와 같은 방법을 통해 map을 사용하여

split의 결과를 int 형으로 저장이 가능하다!!

 

+ TMI

 

이번에는 dx dy 사용해서 저번 문제보단

효율적으로 해결한 것 같다.

 

사실 중간에 dx가 x니까 col을 조절하고

dy가 y니까 row를 조절한다고 생각했는데

 

막상 짜놓은 코드를 보니까

반대로 하고 있었다.

 

사실 구현에 상관은 없다!

어차피 내가 임의로 배열로 만들어서

문제를 해결하는거니까..?!

 

근데 그래도 생각한대로 하는게

나중에 코드 확인할 때도 편할 것 같아서

생각했던 그림에 맞게

코드를 수정했다.

 

이번엔 bfs로 구현했는데

확실히 dfs와는 다른 매력이 있넹ㅋㅅㅋ

 

그럼 끝!

 

참고 사이트) https://dojang.io/mod/page/view.php?id=2179

파이썬 코딩 도장: 6.4 입력 값을 변수 두 개에 저장하기