<프로그래머스> 네트워크

알고리즘

koyuchang 2021. 1. 19. 23:49

코딩테스트 연습 - 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있

programmers.co.kr

풀이

DFS와 BFS를 사용해서 풀이가 가능한 문제다. BFS를 사용하였는데 DFS를 사용하지 않은 이유는 n의 범위가 200까지 길래 시간 초과 문제가 발생할 수도 있다고 판단하여 BFS를 사용하였다.

2차원 배열을 보면 대칭이므로 i<=j일때 까지는 넘어갔다. 그리고 ArrayList배열에 양방향으로 add를 해주었다.

BFS코드에서 한번 방문한 노드는 방문체크를 해서 다시는 방문하지 않게 하였고 한번 탐색으로 방문 체크가 끝나면 network 배열을 +1해 주어서 네트워크의 개수를 계산하였다.