https://school.programmers.co.kr/learn/courses/30/lessons/43162
def dfs(x, computers, visited):
visited[x] = True
print(visited ,{2})
for a, b in enumerate(computers[x]):
print(visited ,{1})
if b == 1 and (not visited[a]):
dfs(a, computers, visited)
print(visited)
def solution(n, computers):
cnt = 0
visited = [False] * n
for i in range(n):
if visited[i] == False:
print(visited ,{3})
dfs(i, computers, visited)
cnt += 1
print(i)
return cnt
위의 코드를 기준으로 print문을 찍어본 결과이다.(주요 코드별로 print문을 찍었으므로 보면 훨씬 수월할 것)
알고리즘 설명 - 2번 테스트 셋 기준
처음에 [false, false, false]겠지 그럼 일단 dfs를 만났으니까 [true,false,false]로 바뀜 그리고 dfs함수문에서 0번컴퓨터를 기준으로 for문 수행 근데 이미 a=0일때 visited가 true기 때문에 한번 빠꾸 먹고 다시 a =1일 때 for문 수행 이번엔 수행이 되어서 dfs재귀를 만나고 [true, true, false]로 변환 그럼 다시 1번 컴퓨터를 기준으로 for문 수행 이미 [true, true, false]니까 두번 빠꾸먹고 1번 컴퓨터가 [1,1,1]이니까 index[2]에 걸려서 dfs문 실행 그래서 최종적으로 [true, true, true]
solution 메인함수 입장에서는 dfs함수 실행후 dfs()에서 이미 재귀로 인해 전체 모두 true가 되었기 때문에 한번도 걸리지 않아 cnt =1인 것
회고
1차 - 혼자 풀기는 힘들었다 아직 dfs/bfs문제는 어색하다. 근데 확실한건 dfs/bfs문제는 풀이가 그리 길지 않다. 이해만 하면 풀만할 듯 일단 컴퓨터가 n대 있으므로 visited 배열을 세워 각 computer마다 접근을 할 수 있는지 visited = [fasle] * n을 만들고 visited 배열에 맞춰 재귀적으로 접근하는 과정을 이해했다. 다른 문제에도 이것들을 적용할 수 있는지 확인할 것
2차 - 전체적으로 어려운문제다 visited도 생각하면서 그 안의 3개의 computer에 대한 네트워크 연결 여부도 확인해야하므로 고려할게 많은 문제다 dfs 재귀에 대한 정확한 이해가 없이는 풀기 힘들 것
