323. 네트워크
1) 어떤 전략(알고리즘)으로 해결?
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 를 풀면 안된다. 궁극적인 목적, 핵심은 해당 사이클을 찾아내는 것이기 때문입니다.
