DFS, BFS를 아무리 공부해도 이해되지 않을 때

DFS, BFS의 개념에 대해 안다.

근데 코드를 보면 잘 이해가 가지 않는다.

 

저렇게 하는게 방문이 되는거라고?

그냥 배열 쭉 탐색 한번 하는게 방문한거라고?

아니 애초에 저 2차원 배열이 그래프랑 같은거야?

사실 볼 때마다 이해하기 어려웠다.

 

이번에 프로그래머스 "네트워크" 문제를 풀면서 계속 고민하고,

코딩에 써먹어본 결과 몇가지 결론이 도출됐고,

이해가 잘 된 것 같다.

 

return 하는 결과물(visited 1차원 배열)은
방문했던 노드들을 방문 순서대로 나열한 것이다.

위 그림과 같다면 visited 배열은
[1, 2, 3, 4, 5, 6, 7, 8, 9]
이 되어 return 될 것이다.

dfs가 한번 끝나면 하나의 그래프가 다 방문된다.
즉, 주어진 인풋이 여러개의 그래프가 있다면,
다른 반복문(for / while)을 써서 다시 탐색해야한다.
※코드에 따라 이때는 시작점(root)을 다시 설정해줘야 할 수도 있다.

BFS와 DFS는 딱 한개 차이가 난다.
stack을 쓰는 것과 queue를 쓰는 것이다.

 

그렇게 문제를 풀고 네트워크의
다른사람의 코드를 보니,

보통 타인의 코드를 보면 깜짝 놀랄만큼 간결한 답이 있어서
아 정말 난 멀었구나.. 라고 생각이 들지만,

이번 문제는 다 제각각이다.

시간복잡도가 심각한 답변도 있었고,
내가 맨 처음에 발상했던 것 처럼 DFS, BFS가 아닌 꼼수를 쓴 코드도 있었다.
그만큼 정해진 답이 없는 문제인 것 같다.

 

간단한 문제지만

문제가 해결될때 양손들고 소리를 지르며 테스트케이스가 통과되는 것을 봤다.

난 역시 천성 개발자 인가봥 헤헤