알고리즘
[BOJ] 2178번 - 미로 탐색 문제와 마찬가지로 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위한 별도의 클래스(Vertex)를 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야 한다. 나이트는 최대 8방향으로 이동할 수 있기 때문에 미로 탐색 문제에서 설명했던 것과 마찬가지로 탐색에 위험부담이 있는 DFS를 사용하지 않고 탐색 효율이 좋은 BFS를 사용한다. 또한, 미로 탐색 문제에서와 동일하게 나이트가 출발점에서 도착점까지 갈 수 있는 최단거리를 찾기 위해서 각각의 정점에 대한 부모 배열을 만들었고, 탐색이 끝난 후에 도착점으로부터 부모 배열을 타고 올라가서 시작 정점을 찾는 방식으로 최단거리를 구하였다. 미로 탐색 문제와의 차이점은 단지 방향이 4개에서 8개로 늘어났다는 것을 제외하면 완전히 동일한 문제이다.
소스코드
문제링크
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
'Coding Test > Solved' 카테고리의 다른 글
| [BOJ] 백준 2468번 - 안전 영역(with Java) (0) | 2021.07.18 |
|---|---|
| [BOJ] 백준 2231번 - 분해합(with Java) (0) | 2021.07.13 |
| [BOJ] 백준 2798번 - 블랙잭(with Java) (0) | 2021.07.13 |
| [BOJ] 백준 1059번 - 좋은 구간(with Java) (0) | 2021.07.13 |
| [BOJ] 백준 2178번 - 미로 탐색(with Java) (0) | 2021.07.11 |
댓글