[프로그래머스] 네트워크 🌐 (Python) / level3 / DFS

Programmers Logo

 

 

Contents

 

---

 

1.  문제🔥

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

문제 설명과 제한 사항

문제를 요약하자면, 컴퓨터 개수(n)과 각 컴퓨터의 연결 정보(computers)를 줬을 때, 연결 성분의 개수를 출력하는 문제입니다.

 

1) 예제 입출력❄️

예제 입출력

첫번째 예제를 보겠습니다. n=3으로 컴퓨터는 3대이고, computers는 아래와 같은  형태입니다.

[[1,1,0],
 [1,1,0],
 [0,0,1]]

이 2차원 배열의 의미는 i행 j열에 1이면 i번 컴퓨터와 j번 컴퓨터는 연결된 것입니다. 즉, 대각 성분은 자기 자신이기 때문에 항상 1이고 그 외에, 1행 2열과 2행 1열이 1로 채워져 있습니다. 즉 1번 컴퓨터와 2번 컴퓨터가 연결된 것입니다. 아래 사진을 보면, 연결 성분이 총 2개인 것을 알 수 있습니다.

2. 핵심 논리☢️

핵심 논리는 컴퓨터 별로 방문 표시할 visted 리스트과 DFS를 이용한 것입니다. 한 컴퓨터에 연결된 모든 컴퓨터를 다 방문하며 visited에 표시하고, 방문하지 않은 컴퓨터에 대해서 또 연결된 컴퓨터를 모두 방문하고, 이런 식으로 연결 성분의 개수를 찾아가는 것이 핵심입니다.

3. 풀이 코드✅

def solution(n, computers):
    visited=[0]*n # 방문 표시 리스트
    answer=0 # 연결 성분 개수 초기화
    def dfs(pc): # dfs로 연결된 부분 쭉 탐색
        visited[pc]=1 # 방문 표시
        for idx,c in enumerate(computers[pc]): # 해당 컴퓨터에 연결된 컴퓨터 반복
            if c and visited[idx]==0:
                dfs(idx)
                
    for pc in range(n):      # n개의 컴퓨터에 대해 
        if visited[pc] == 0: # 방문 안했으면 
            dfs(pc)          # dfs 진행
            answer+=1        # dfs 1번 진행할때마다 +=1
    return answer

방문 표시 리스트(visited)를 n개의 [0]으로 초기화 합니다. answer는 연결 성분 개수가 들어갈 변수입니다. 

dfs함수는 방문할 컴퓨터의 인덱스를 pc로 전달받아서, 방문 표시를 합니다. 그리고, computers 2차원 배열에 대해 enumerate로 idx(컴퓨터의 인덱스)와 c(idx 컴퓨터와 연결 여부)를 받아서 if c and visited[idx]==0: (연결되어있고, 해당 컴퓨터 방문하지 않은 경우) dfs를 재귀 호출해줍니다. 즉, dfs함수에 컴퓨터가 들어오면, 해당 컴퓨터와 연결된 모든 컴퓨터를 DFS 방식으로 순회하며 방문 표시를 하는 함수입니다.

다음으로 for pc in range(n): 으로 각 컴퓨터를 반복하며, 방문하지 않은 경우 dfs를 호출하고, dfs가 끝나면 해당 컴퓨터에 연결된 모든 컴퓨터를 다 순회하며 방문 표시를 했다는 의미이므로, answer(연결 성분 개수)에 1을 더해줍니다. 그렇게 for 문이 끝나고 answer를 리턴해주면 모든 연결 성분의 개수가 출력됩니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/Programmers/blob/master/Level3_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.ipynb

GitHub - netsus/Programmers: Programmers algorithm test code

 

 

Reference)
1. Programmers Logo: https://programmers.co.kr/