[프로그래머스/파이썬] 네트워크

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

프로그래머스

프로그래머스 Level 3 정도의 문제지만, 백준으로 치면 다른 트릭이나 복잡한 구현이 없는 기본적인 bfs/dfs 문제라서 골드 4-5정도 될 것 같다.

 

아무튼, 이 문제의 풀이에 대해 알아보자

 

문제에서 찾고자 하는 것은 '연결된 영역의 개수' 라고 할 수 있다.

n은 반드시 1 이상, 즉 주어진 그래프에는 노드 1이 반드시 존재함을 알 수 있다.

 

1을 기점으로, 재귀 형식의 dfs를 이용해 아직 방문하지 않은 다음 노드가 존재한다면 계속 탐색해준다.

이 때 한 번의 dfs 탐색이 종료된다는 것은 서로 연결된 하나의 영역을 모두 탐색했다는 뜻이므로 정답을 하나 증가시켜주면 된다.

 

그래프 입력도 친절히 이중리스트로 주어져서 그래프 상에서 dfs/bfs를 연습하기 좋은 문제인듯 하다.

def dfs(now, visited, n, computers):
    visited[now] = True
    
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and now != next and visited[next]==False:
            dfs(next, visited, n, computers)
            
    return 0
            
def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for i in range(n):
        if visited[i] == False:
            dfs(i, visited, n, computers)
            answer += 1
    
    return answer