[Algorithm] 네트워크

코딩테스트 연습 - 네트워크

헐 ㅋ 풀었다. 이렇게 한 걸음씩 ㄱㄱ

소요 시간 

13:42 - 14:13 (총 31분)

 

해결 과정

우선, DFS/BFS 문제라는 것을 알고 있는 상태였다. 

문제 자체가 그래프로 주어졌는데, 연결이 끊어진 상태가 몇 개인지를 찾는 문제였다. 우선 연결되어 있는 것을 먼저 다 돌면, 이걸 1개로 처리하고 아직 돌지 않은 것들 중 또 다시 연결되어 있는 것을 다 도는 형태로 가야했다. -> DFS를 여러 번 돌리자. 

코드는 DFS 코드 형식을 참고하며 이 문제에 맞게 변형시켰다.

나의 풀이

def DFS(start, computers, visited, n):
    visited[start] = True
    for i in range(n):
        if start != i and computers[start][i] == 1 and visited[i] == False:
            DFS(i, computers, visited, n)
            
def solution(n, computers):
    visited = [False] * n
    count = 0
    
    while False in visited:
        # 가장 첫번째 False 인덱스
        DFS(visited.index(False), computers, visited, n)
        count += 1
    return count​

그냥 일단 순서대로 SUDO 코드도 좋으니 쭉 써보고, 그 때 그 때 필요한 거 있으면 저렇게 파란색으로 해놓고 코드 작성할 때 처리하기. 중복 if 문을 뒀는데, 하나로 합쳐도 될 것 같아서, 코드 작성 단에서 합쳤다. 

다른 풀이