백준 18352번: 특정 거리의 도시 찾기 (JAVA) <BFS>

 

문제 해석

 

단방향 그래프가 주어진다. 

출발지를 입력값으로 지정해주고 출발지에서 시작해 최단거리 K를 만족하는 모든 도시를 출력해야 한다.

 

알고리즘

 

처음에는 모든 가능한 경우를 모두 탐색해야 한다 생각하여 인접행렬을 이용해 DFS를 구현하였다.

 

하지만 그 결과 메모리 초과 오류가 발생하였다. 인접행렬로 구현하여 불필요한 메모리까지 모두 사용한다 생각하여 

연결 리스트를 활용해 DFS를 재구현하였다.

 

 

연결 리스트를 활용해 불필요한 메모리 사용을 줄였지만 그럼에도 메모리 초과가 발생하였다.

또 어느 부분에서 메모리를 줄일 수 있을까 생각을 해보았다.

메모리를 줄일 수 있는 부분은 이제 방문 기록을 체크하기 위해 사용한 visited와 최단거리를 저장하기 위한 result이다.

그런데 기본적으로 최단거리 문제를 푸는데 BFS를 활용하지 않은 나 자신이 이상하다 생각하였다.

BFS 사용시 비록 Queue를 사용하긴 하지만 방문 기록을 체크하기 위해 사용한 배열보다는 적은 메모리를 차지하고 

BFS 자체가 최단거리를 반환하기 때문에 최단거리를 체크하기 위해 사용한 cnt 변수가 필요 없다.

 

코드