백준 16948번: 데스 나이트 (파이썬)

 

항상 그래프 탐색 이론 해야지만 하고 넘어가다가 결국 랜덤 문제에서 마주침

나 혼자 다 풀었다고 할 수는 없지만 원래 시작이 반이니가 반만 내가 더 하면 그래프 이론 할 수 있겠지 머

 

from collections import deque

def bfs(r1, c1):
  # 방문할 위치 q
  q = deque([(r1,c1)])
  
  # 방문한 위치에 언제 방문했는지
  visited[r1][c1] = 0
  
  while q:
    r, c = q.popleft()
    # 나이트가 갈 수 있는 방향
    for rr, cc in [(-2,-1),(-2,1),(0,-2),(0,2),(2,-1),(2,1)]:
      # 현재 위치에서 이동했을 때 위치
      nr, nc = r+rr, c+cc
      # 체스판 위에 있고(양수) 아직 방문한 곳이 아니면
      if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == -1:
        # 방문할 곳에 저장
        q.append((nr,nc))
        # 방문 표시
        visited[nr][nc] = visited[r][c] + 1


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

# 체스판
visited = [[-1]*N for _ in range(N)]
bfs(r1,c1)
print(visited[r2][c2])

 

이해한대로 그려보자면 일단 체스판을 만든다

체스판에서 처음 나이트가 서있는 위치를 제외한 모든 수를 -1로 만든다

 

나이트가 갈 수 있는 모든 방향의 수를 더하고 뺀다 

계산한 수가 체스판 위에 올라가 있고 (모두 양수)  아직 방문하지 않은 곳이라면 방문할 리스트에 올린다

방문할 리스트에 올렸으면 방문했다고 표시해준다

 

다른 문제들도 풀어보며 참고자료 없이도 가능하도록 만들기