그래프와 순회. [7562]

[1. 문제 설명]

현재 나이트 위치에서 다음 나이트 위치까지 이동 할 때, 필요한 최소 이동 횟수

 

 

[2. 풀이 접근]

BFS 탐색은 DFS 와 달리 특별한 성질이 있다.

그 성질은 각 정점을 최단경로 방문한다는 것이다.

(단, 이 경우 Edge 의 weight 라는 개념이 없거나, 모든 weight 가 같아야 한다.)

 

아래와 같은 그래프를 정점1에서 시작해서 DFS 로 탐색 할 때

(인접한 정점을 오름차순으로 방문한다 가정)

정점6에 방문하기 위해서는 4개의 edge 를 거쳐야만 한다.

 

하지만, BFS로 탐색 시, 총 2개의 edge 만을 거치면 된다.

 

따라서, bfs 로 나이트를 특정 위치에 도달 할 때 가지 각 방향으로 이동시키면 된다.

 

 

[3. 코드]