티스토리 뷰
[Silver I] 데스 나이트 - 16948
성능 요약
메모리: 32452 KB, 시간: 108 ms
분류
너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
문제 설명
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.
데스 나이트는 체스판 밖으로 벗어날 수 없다.
입력
첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.
출력
첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.
# 체크판의 크기 n
from collections import deque
dx, dy = [-2, -2, 0, 0, 2, 2], [-1, 1, -2, 2, -1, 1]
n = int(input())
# 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동
r1, c1, r2, c2 = map(int, input().split())
graph = [[0] * n for _ in range(n)]
def bfs():
visitied = [[0] * n for _ in range(n)]
visitied[r1][c1] = 1
q = deque()
q.append((r1, c1))
while q:
x, y = q.popleft()
for i in range(6):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and not visitied[nx][ny]:
visitied[nx][ny] = visitied[x][y] + 1
q.append((nx, ny))
if nx == r2 and ny == c2:
return visitied[nx][ny] - 1
return -1
print(bfs())
'코딩테스트 > 백준' 카테고리의 다른 글
파이썬 | 2589_보물섬_G5 (0) | 2022.07.07 |
---|---|
파이썬 | 16918 봄버맨 _ S1 (0) | 2022.07.04 |
파이썬 | 12671. 돌다리 _ S1 (0) | 2022.06.23 |
파이썬 | 2583 영역 구하기 S1 (0) | 2022.06.19 |
파이썬 | 2468 안전영역 S1 (0) | 2022.06.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 코딩테스트
- 1063
- Git
- 크레인 인형뽑기 게임
- 오
- K번째수
- 백준
- 카카오 코딩테스트
- 2019 카카오 개발자 겨울 인턴십
- 프로그래머스
- 자료표현
- 브루트포스
- solved.ac
- stack
- java
- 인형뽑기
- 알고리즘
- 프로그래머스 # 음양더하기
- 2진수
- 킹
- 자료구조
- 구현
- 10진수
- ASCII코드
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함