[python] 프로그래머스 - 네트워크

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

문제 설명

프로그래머스의 네트워크 문제는 여러 컴퓨터가 연결되어 있는 네트워크의 개수를 구하는 문제입니다.
컴퓨터들의 연결 정보는 2차원 리스트(인접 행렬)로 주어지며,
연결된 컴퓨터들은 하나의 네트워크를 구성합니다.
문제의 목표는 주어진 컴퓨터들의 연결 정보로부터 총 네트워크의 개수를 찾는 것입니다.

---

문제 접근 방식

1. 방문 배열(visit) 생성

   • 각 컴퓨터가 이미 네트워크 탐색에 포함되었는지 확인하기 위해 visit 리스트를 생성합니다.

2. 깊이 우선 탐색(DFS) 활용

   • 한 컴퓨터에서 시작하여 연결된 모든 컴퓨터들을 재귀적으로 탐색합니다.
   • 탐색 중 방문한 컴퓨터는 visit 리스트를 통해 중복 방문을 방지합니다.

3. 네트워크 수 카운팅

   • 아직 방문하지 않은 컴퓨터가 발견되면 DFS를 실행하고, 새로운 네트워크로 간주하여 카운트를 증가시킵니다.

---

문제 풀이

def solution(n, computers):
    answer = 0
    visit = [False] * n

    def dfs(i):
        visit[i] = True
        print('i : ', i)
        # 현재 컴퓨터 i와 연결된 다른 컴퓨터 j를 확인
        for j in range(i+1, n):
            print('j : ', j)
            if computers[i][j] == 1:
                dfs(j)

    for i in range(n):
        if not visit[i]:
            dfs(i)
            answer += 1
    return answer

주의사항 및 팁

방문 여부 확인:
DFS 함수 내에서 방문 여부를 체크하여 무한 재귀나 중복 방문을 피해야 합니다.
인접 행렬 탐색:
현재 코드는 for j in range(i+1, n):로 진행되는데,
이는 i보다 큰 인덱스의 컴퓨터만 확인하므로,
문제 조건(대칭 행렬, 자기 자신 포함)에서 올바르게 동작하는지 확인이 필요합니다. 일반적인 경우에는 모든 j에 대해 검사(for j in range(n):)하고,
if computers[i][j] == 1 and not visit[j]:와 같이 방문 여부를 함께 체크하는 것이 안전합니다.
디버깅 출력 제거:
최종 제출 시에는 print() 문을 제거하여 디버깅 출력 없이 실행하도록 합니다.