문제는 주어진 맵에 따라 나뉘어지는 네트워크의 갯수를 맞추는 문제이다. 맵은 각 노드끼리 연결 유무에 대한 정보가 0과 1로 주어졌다. bfs와 dfs 모두 다 풀이에 활용할 수 있으나 한 붓 그리기와 같은 형태라고 생각해서 dfs를 먼저 떠올렸다.
나의 풀이는 다음과 같다.
주어진 노드 간 연결 정보를 맵으로 변환한다. 예를들어 temp_map[i]는 i번째 노드에 연결된 노드들의 idx 가 담겨진다.
visited list를 선언한다. ⇒ 방문한 노드는 방문하지 않기 위함.
0 ~ n-1까지 노드들을 체크하며, 방문한 적이 없는 노드라면 dfs를 돌린다.
3)에서 dfs가 실행된 횟수가 곧 네트워크의 갯수를 의미한다.
오늘의 문제는 기본 중의 기본에 해당하는 dfs 문제였다. 14일차와 마찬가지로 크게 어렵진 않았으나 빈출 유형이니 앞으로 꾸준히 풀어봐야겠다.
문제 풀이 전, 어떻게 풀지 미리 구상해볼 것. + 다양한 예외 상황에 대해 생각해볼 것.