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

1. 문제정보

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

프로그래머스

 

2. 풀이과정

레벨 3이라서 조금 긴장했는데 문제를 보았을 때 "그냥 DFS/BFS 돌리면 되는거아니야?" 하고 구현했고 테스트케이스를 실행했을 때 정상적으로 통과되었다. 하지만 제출 과정에서는 대부분 실패하게 됐는데 그 이유를 이해하는데 시간이 조금 소요되었다.

 

결론부터 말하자면 주어진 배열정보를 그대로 DFS/BFS를 실행하면 정답을 구할 수 없다. 아래와 같이 정보가 주어졌을 때 단순히 탐색을 돌리면 7의 답을 얻지만 이것은 정답이 아니다.

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

 

문제의 의미를 파악하고 위의 데이터를 보면 네트워크1(1번-5번), 네트워크2(2번), 네트워크3(3번), 네트워크4(4번)으로 총 4개의 네트워크만 필요하다는 것을 알 수 있다.

 

3. 소스코드

from collections import deque
def solution(n, computers):
    graph = [[] for i in range(n)]
    visited = [False] * n
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                graph[i].append(j)
    
    answer = 0
    for i in range(len(graph)):
        # 이미 방문한 컴퓨터라면 제외
        if visited[i] == True:
            continue
            
        q = deque()
        q.append(i)
        answer += 1
        
        while q:
            p = q.pop()
            # 방문체크 후 방문처리
            if visited[p]:
                continue
            visited[p] = True
            
            # 연결된 컴퓨터 중 미방문 처리된 컴퓨터 큐에 추가
            for link in graph[p]:
                if visited[link]:
                    continue
                q.append(link)
    return answer

 

4. 배운점

연결 정보라고 주어진 배열을 무지성으로 탐색돌리면 위험하다는 것을 알았다. 그렇다면 길찾기(벽으로 막혀있고 등등)의 문제에서는 배열을 탐색돌려도 가능하겠지만 이처럼 A와B의 연결 정보를 배열로 표현한 경우 한번 더 고민해봐야한다.