접근
주어진 것을 정리 : 노드(컴퓨터)의 갯수, 비방향성, 연결선
첫 시도: key(컴퓨터) - value (key와 연결된 컴퓨터) 구조의 dictionary 작성 시도
-> 못품 ㅎ ㅠ
dfs로 접근 : 이미 방문한 노드를 체크하기 위해 visited 리스트 생성
-> 원소는 모두 0으로 채우고, while문으로 0이 나오지 않을 때 까지 체크
현재 방문중인 노드(컴퓨터)와 연결된 컴퓨터를 모두 찾기 위해 dfs 스택 선언
dfs 스택에 append될 조건은, 아직 방문하지 않은(visited[i]==0) 동시에(and) 현재 방문중인 노드와 연결 돼(computers[curr][i]) 있을 때
풀이 1) 반복문 사용
def solution(n, computers):
visited = [0] * n
result = 0
dfs = list()
while 0 in visited:
dfs.append(visited.index(0))
while dfs:
curr = dfs.pop()
visited[curr] = 1
for i in range(n):
if computers[curr][i] == 1 and visited[i] == 0:
dfs.append(i)
result += 1
return result
풀이 2) 재귀문 사용
def solution(n, computers):
answer = 0
visited = [0] * n
def dfs(computers, visited, start):
stack = [start]
while stack:
j = stack.pop()
visited[j] = 1
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
stack.append(i)
return
i=0
while 0 in visited:
if visited[i] ==0:
dfs(computers, visited, i)
answer +=1
i+=1
return answer
아쉬운 점 및 정리