[알고리즘/Python] 프로그래머스 - 네트워크 (DFS)

프로그래머스 문제

풀이1

solution 함수

• n : 컴퓨터의 개수
• computers : 연결에 대한 정보가 담긴 2차원 배열
• return : 네트워크의 개수

dfs 함수

• graph : computers
• v : 현재 index
• visited : 방문처리를 위한 1차원 배열

자세한 풀이

• 연결되지 않은 네트워크가 있을수도 있으므로 index 를 n 만큼 반복하며 dfs 함수를 호출한다.
• 처음 방문하는 경우에는 새로운 네트워크가 시작되는 것과 같다.
  • count 를 증가시킴
  • 현재 index 를 방문처리 시킴
  • 이미 방문처리 되어있다면 네트워크가 연결되어 있으므로, count하지 않음
• graph 를 반복하며 방문하지 않은 노드에 대해 방문처리, dfs 재귀호출

count = 0
def dfs(graph, v, visited):
    global count
    if not visited[v]:
        count += 1
        visited[v] = True

    # DFS 수행
    for i, node in enumerate(graph[v]): 
        if i == v or node == 0:
            continue
        if not visited[i]:
            visited[i] = True
            dfs(graph, i, visited)

def solution(n, computers):
    global count
    count = 0
    visited = [False] * n
    for i in range(n):
        dfs(computers, i, visited)
    return count

 

풀이2

• index 를 n 만큼 반복하며 연결되지 않은 네트워크를 찾는다.
  • visited[i] == False 인 경우에만 dfs 함수를 호출한다.
• dfs 를 호출하는 반복문 내에서 방문처리에 대한 if 문 추가
  • dfs 함수 내에서 방문처리에 대한 if 문 제거
• dfs 를 호출하는 반복문 내에서 count 증가
  • dfs 를 호출하는 solution 함수 내에서 count 변수 지정

def dfs(graph, v, visited):
    # 방문처리
    visited[v] = True 

    # DFS 수행
    for i, node in enumerate(graph[v]): 
        if i == v or node == 0:
            continue
        if not visited[i]:
            dfs(graph, i, visited)

def solution(n, computers):
    count = 0
    visited = [False] * n
    for i in range(n):
        # 새로운 네트워크가 시작되는 경우
        if not visited[i]: 
            dfs(computers, i, visited)
            count += 1
    return count 
    
print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # return 2
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]])) # return 1

 

정확성 테스트 비교

풀이1

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.06ms, 10.1MB)
테스트 4 〉	통과 (0.08ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.3MB)
테스트 6 〉	통과 (0.42ms, 10.2MB)
테스트 7 〉	통과 (0.03ms, 10.2MB)
테스트 8 〉	통과 (0.31ms, 10.2MB)
테스트 9 〉	통과 (0.20ms, 10.3MB)
테스트 10 〉	통과 (0.20ms, 10.2MB)
테스트 11 〉	통과 (1.91ms, 10.2MB)
테스트 12 〉	통과 (1.26ms, 10.3MB)
테스트 13 〉	통과 (0.63ms, 10.2MB)

풀이2

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.1MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.24ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.18ms, 10.2MB)
테스트 9 〉	통과 (0.11ms, 10.1MB)
테스트 10 〉	통과 (0.10ms, 10.1MB)
테스트 11 〉	통과 (0.86ms, 10.3MB)
테스트 12 〉	통과 (0.74ms, 10.2MB)
테스트 13 〉	통과 (0.32ms, 10.1MB)

---

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

이번 문제를 풀면서

• 문제에서 DFS / BFS 를 이용하라고 친절하게 알려줬다.
• 다른 문제를 풀 때 "DFS / BFS 를 이용해야한다" 는 힌트를 찾아봐야겠다.
• BFS 풀이 참고 - 링크