게임 맵 최단거리 - 프로그래머스, c++

 

 

- 문제 풀이

깊이/너비 우선 탐색 (DFS/BFS) 을 사용하는 문제였다.

더 빨리 최단 거리의 길을 찾기 위해 그 중에서도 너비 우선 탐색(BFS)을 사용했다.

 

< BFS 구현 방법 >

1. 필요한 배열, 큐 등을 선언한다.

    - visited[] 배열을 선언해 해당 노드에 이미 방문했는 지 안 했는 지 확인할 예정

    - 큐로 사용할 vector or queue 선언

2. BFS 함수를 만든다.

    - 인자로 받은 노드를 visited = true로 바꿔주고 큐에 해당 노드를 넣기

    - while문을 통해 큐가 비어있을 때까지 탐색

3. main 에서 연결된 노드끼리를 연결한다.

4. main 에서 탐색을 시작하고 싶은 노드를 넣어 BFS 함수를 실행한다.

 

 

- 코드

제출한 코드는 다음과 같다.

(코드 참고: https://ansohxxn.github.io/programmers/114/ )