📘[DFS] 네트워크

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

답안

def DFS(n, computers, com, visited):
    if visited[com] == True:
        return
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1:
            DFS(n, computers, connect, visited)

def solution(n, computers):
    answer = 0
    visited = [ False for _ in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1
    return answer

"""
# 백준이나 ide에서 할 때
if __name__ == "__main__":
    n = 3
    computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    print(solution(n, computers))  # 2
    n = 3
    computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
    print(solution(n, computers))  # 1
"""

풀이

우선 보통의 완전탐색 문제는 BFS, DFS 모두 사용이 가능하다. 결국 완전탐색만 하면 끝이니까.

이 번에는 DFS로 문제를 풀어봤다. (결국 혼자 힘으로 풀진 못했고, 답안을 참고함.. 계속 이렇게 해서 실력을 키워가자)

하지만 보통 최단거리, 네트워크 등의 문제 들은 BFS가 유리하다고 알고있다.

BFS로도 해보긴 함.

우선 DFS는 가장 깊게 들어갔다가 나오는 탐색 방법인건 알고있다.

그러면 네트워크의 개수를 구하려면 네트워크의 구성 요소인 엔드포인트가 필요하다.

여기선 이걸 com으로 했다. (시작 computer라는 의미로)

동작 순서는 다음과 같다.

def DFS(n, computers, com, visited):
    if visited[com] == True:
        return
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1:
            DFS(n, computers, connect, visited)

1. 방문기록(visited)에서 시작 노드에 대한 값이 True이면 return (방문은 한 번만 하므로, 이미 방문했으면 재귀 종료)
2. 방문기록에 없던 노드면 True로 바꿔주고 본격 DFS 시작
3. for connect in range(n)으로 했는데, 보통 graph[node]를 순회하더니 여기서는 왜?
   • 문제에서 computers를 2차원 배열로 줬고, 각 컴퓨터들의 인덱스가 [0, 1, 2]니까 range(3)으로 해도 무방하기 때문으로 이해함.
4. 만약 순회하는 computer가 DFS를 실행하는 컴퓨터인 com과 같지 않아야 함.
   • 각각의 컴퓨터는 스스로 네트워크가 될 수 있음. 즉, (0, 0), (1, 1), (2, 2)는 어차피 1임 (확인할 필요 없음)
5. computers[com][connect] == 1이면
   • 1이면 연결되어있는 거니까 체크
6. 4, 5번 조건 동시에 만족하면, DFS를 다시 실행함.

def solution(n, computers):
    answer = 0
    visited = [ False for _ in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1
    return answer

• 여기서는 visited를 선언하고
• for 문으로 순회를 하며 DFS를 실행하는데..
• DFS는 재귀로 동작하니까, 이 DFS가 동작이 끝나면 answer을 1증가 시키면 됨.

회고

• answer += 1 부분이 사실 제일 이해 안됐던 부분 중 하나임.
• BFS의 풀이도 봐야함..!