[프로그래머스 / 깊이/너비 우선 탐색(DFS/BFS) / Python] 네트워크

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

 

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

 

---

풀이 코드

 

수정 전

def dfs_stack(graph, start, visited):
	stack = [start]

	while stack:
		node = stack.pop()
		visited.append(node)
		for idx, node_node in enumerate(graph[node]):
			if idx not in visited and node_node:
				stack.append(idx)

	return visited

def solution(n, computers):
    answer = 0
    
    visited = []
    
    for idx in range(len(computers)):
        if idx not in visited:
            dfs_stack(computers,idx,visited)
            answer += 1
    return answer

 

 

수정 후

코테 스터원 선배님이 좋은 아이디어를 알려주셔서..! 수정했다.

if ~ not in ~을 쓰면 *n이 되어 시간복잡도가 증가한다.

해서 O(1)로 찾게끔 만들었다!

 

def dfs_stack(graph, start, visited):
	stack = [start]

	while stack:
		node = stack.pop()
		visited[node] = 1
		for idx, node_node in enumerate(graph[node]):
			if visited[idx]==0 and node_node:
				stack.append(idx)

	return visited

def solution(n, computers):
    answer = 0
    
    visited = [0] * n
    
    for idx in range(len(computers)):
        if visited[idx]==0:
            dfs_stack(computers,idx,visited)
            print(visited)
            answer += 1
    return answer

 

확실히 시간이 단축된 것을 볼 수 있다.!

---

풀이 과정

 

 

def solution(n, computers):
    answer = 0
    
    visited = [0]*n
    
    for idx in range(len(computers)):
        if visited[idx] == 0:
            dfs_stack(computers,idx,visited)
            answer += 1
    return answer

이어져 있는 것들을 계속해서 탐색하는 문제이므로 DFS를 이용하였다.

 

1. 문제의 input값이 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 과 같은 인접행렬 형태로 되어있기에 visited값을 리스트의 인덱스 값으로 하였다.

 

2. for문을 돌면서 해당 visited[idx]가 0인 경우만(연결된 네트워크를 찾지 않은 경우만) dfs를 수행하게 했다.

 

3. 문제의 조건인 A-B-C인 경우 한개의 네트워크로 취급한다는 조건에 따라 DFS를 돌 때 마다 네트워크 개수를 +1 해주었다.

 

 

DFS안의 코드를 보면

def dfs_stack(graph, start, visited):
	stack = [start]

	while stack:
		node = stack.pop()
		visited.append(node)
		for idx, node_node in enumerate(graph[node]):
			if visited[idx] == 0 and node_node:
				stack.append(idx)

4. stack이 비어있지 않으면 while을 돌게 조건을 만든 후 stack에 담겨있는 node값을 pop한다.

 

5. 같은 노드를 재방문 하는 일이 없어야 하기 때문에 pop한 node는 visited에다가 넣어준다.

 

6. graph의 node 즉 해당 인덱스의 리스트값들을 하나씩 꺼내어 node_node가 1이면서 이전에 방문하지 않았던 인덱스면 같은 네트워크상에 있다 판단하여 stack에 넣어준다.

 

 

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

코딩테스트 연습 - 네트워크