[프로그래머스] 네트워크 (Python3)

programmers.co.kr/learn/courses/30/lessons/43162

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

from collections import deque
 
def bfs(computers, start, visited):
    queue=deque([start])
    visited[start]=True
    while queue:
        v=queue.popleft()
        for i,computer in enumerate(computers[v]):
            if i==start:
                continue
            if computer==1 and visited[i]==False:
                queue.append(i)
                visited[i]=True
 
def solution(n, computers):
    answer = 0
    visited=[False]*n
    for i in range(n):
        if visited[i]==False:
            bfs(computers,i,visited)
            answer+=1
    return answer

개강 때문에 멘탈이 탈탈탈탈탈 털려서 정신 부여잡고 풀었다.

전형적인 BFS, DFS 탐색 문제.

나같은 경우에는 BFS 로 풀었는데 방문하지 않은 노드에 대해 인접 노드들을 모두 BFS 탐색해주고 answer+1 을 높힌다.

enumerate 써서 start 노드와 탐색 노드 비교할 필요 없다! 어차피 start 노드는 방문처리 해주므로 방문하지 않은 인접 노드 체크하는 과정에서 자동으로 걸러지니까. 결론적으로 말 하면 쓸필요 없었다.

DFS 로 푸는 방법도 있다. 최대한 깊게 탐색하는 거니까 뭔가 이 문제에 더 직관적으로 어울리는 풀이법인 느낌이다.

 

출처: 프로그래머스   김재원 , weronyoungjoon 님

 

이렇게 푸는것도 좋은것 같다. DFS를 이용, 재귀로 쭉 탐색해준 뒤 visited가 모두 True일 때까지 돌리는 방식이다.