def solution(n, computers):
answer = 0
connected = [False] * n
for i in range(n):
for j in range(n):
if computers[i][j] == 1:
if i==j:
continue
else:
if connected[i] and connected[j] ==False :
answer+=1
connected[j] = True
elif connected[j] and connected[i] ==False:
answer+=1
connected[i] = True
else:
connected[i] = True
connected[j] = True
return answer위 코드는 틀렸다... 하지만 처음으로 레벨이 3이상인 알고리즘 문제를 내가 끝까지 작성해보고 예제 하나라도 맞은 것이 너무 기뻤다!!
DFS(재귀함수를 사용해서)를 더 사용할 줄 알아야할 것 같다..
def solution(n, computers):
def dfs(node):
visited[node] = True
for i in range(n):
if computers[node][i] == 1 and not visited[i]:
dfs(i)
visited = [False] * n # 각 컴퓨터의 방문 여부를 저장
answer = 0
for i in range(n):
if not visited[i]: # 방문하지 않은 컴퓨터를 발견하면 DFS 탐색 시작
dfs(i)
answer += 1 # 새로운 네트워크를 발견할 때마다 카운트 증가
return answer
애초에 i와 j를 각각 따로 두지 말고 한 컴퓨터(node)씩 들어가서 각각을 다 확인한 후 node를 true 처리한다... 한 개씩 처리하고 간다는게 인상 깊었다
이해를 위한 단계
dfs(0)에서:
1) visited[0] = True로 처리 -> 이제 visited = [True, False, False]
2) for i in range(n)에서 i=0, computers[0][0] = 1이지만, 이미 visited[0]은 True이므로 무시
3) i=1에서는 computers[0][1] = 1이고, visited[1]은 False이므로 dfs(1)을 호출
dfs(1)에서:
1) visited[1] = True로 처리 -> 이제 visited = [True, True, False]
2) for i in range(n)에서 i=0과 i=1은 이미 방문되었으므로 무시
3) i=2에서는 computers[1][2] = 0이므로 연결되지 않았고, 탐색을 중단.
dfs(1)이 끝나면 dfs(0)도 끝!! => 이제 첫 번째 네트워크가 탐색되었으므로 answer를 1로 증가시킴
다음 루프에서 i=1이지만, visited[1] = True이므로 이미 탐색된 컴퓨터이므로 무시
: a->b, b->c 는 a->c이므로 굳이 따로 a->c를 확인하지 않아도 된다
dfs(2)에서:
1) visited[2] = True로 처리 -> 이제 visited = [True, True, True]
2) for i in range(n)에서 i=0과 i=1은 연결되지 않았고(computers[2][0] = 0, computers[2][1] = 0), i=2는 이미 방문되었으므로 탐색을 중단
3) dfs(2)가 끝나면 두 번째 네트워크가 탐색되었으므로 answer를 1로 증가
answer=2이며, 네트워크도 2개이다.
코딩테스트 알고리즘 고득점 문제 3일차 풀이하면서 처음으로 예제를 맞춰봐서 매우 행복했다.. 다음엔 꼭 2개를 맞춰야겠다
