파이썬 알고리즘 323번 | [프로그래머스 - 네트워크]

323. 네트워크

1) 어떤 전략(알고리즘)으로 해결?

• dfs

2) 코딩 설명

• dfs 를 통해서 한번에 visit 한 곳들을 하나의 사이클로 분류해주었습니다.

<내 풀이>

from collections import defaultdict 
import sys

sys.setrecursionlimit(100005)

def solution(n, computers):
    answer = 0
    relation = defaultdict(list) 
    for i in range(n) : 
        for j in range(n) : 
            if computers[i][j]==1 and i!=j : 
                relation[i].append(j)
                relation[j].append(i)
    visited = [False for _ in range(n+1)]
    
    def dfs(node) : 
        for next_node in relation[node] : 
            if visited[next_node] == False : 
                visited[next_node] = True 
                dfs(next_node)
        
    for now_node in range(n) : 
        if visited[now_node]==False :
            visited[now_node] = True
            dfs(now_node)
            answer+=1 
    
    return answer

<반성 점>

<배운 점>

• 옛날에 dfs 배울 때 헷갈렸던 포인트가 어떤 문제에선 visited 를 체크했다가 풀고, 어떤 문제에서는 한번 체크하면 풀지 않는 것이었다.
• 이번 문제 + 순열 그래프 + 유니온 파인드 (트리, 노 사이클) 쪽을 어제 오늘 파보면서 깨달았습니다.
• 모든 경우를 탐색해야 하는 경우에는 a를 방문하든지, b를 방문하든지 둘 다 체험해야 하기에 viisted 를 체크했다가, 풀고 다음 b 노드로도 가봐야 한다.
• 그러나 사이클 체크, 트리 체크의 경우에는 양방향이 아니고, 한 사이클을 찾을 때 한번 방문한 곳은 이미 탐색한 사이클이라는 것이다. 이런 경우에는 visited 를 풀면 안된다. 궁극적인 목적, 핵심은 해당 사이클을 찾아내는 것이기 때문입니다.