티스토리 뷰
문제 출처:programmers.co.kr/learn/courses/30/lessons/43162
코딩테스트 연습 - 네트워크
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있
programmers.co.kr
풀이
DFS와 BFS를 사용해서 풀이가 가능한 문제다. BFS를 사용하였는데 DFS를 사용하지 않은 이유는 n의 범위가 200까지 길래 시간 초과 문제가 발생할 수도 있다고 판단하여 BFS를 사용하였다.
2차원 배열을 보면 대칭이므로 i<=j일때 까지는 넘어갔다. 그리고 ArrayList배열에 양방향으로 add를 해주었다.
BFS코드에서 한번 방문한 노드는 방문체크를 해서 다시는 방문하지 않게 하였고 한번 탐색으로 방문 체크가 끝나면 network 배열을 +1해 주어서 네트워크의 개수를 계산하였다.
코드
'알고리즘' 카테고리의 다른 글
| <프로그래머스> 단어 변환 (0) | 2021.01.30 |
|---|---|
| <프로그래머스> 섬연결하기 (0) | 2021.01.23 |
| <프로그래머스> 2 X n 타일링 (0) | 2021.01.19 |
| <프로그래머스> [3차] 압축 (0) | 2021.01.19 |
| <프로그래머스> 방금 그곡 (0) | 2021.01.18 |