📖 Problem
프로그래머스 - 고득점kit - DFS/BFS - 네트워크 (Level3)
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 예
| n | computers | return |
|---|---|---|
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
🔍Institution
DFS란 무엇인지, 어떻게 풀면 좋을지 chatGPT에게 물어보았다.
chatGPT - “What is DFS?”
DFS stands for Depth-First Search, which is a graph traversal algorithm that starts at a given node and explores as far as possible along each branch before backtracking. The algorithm can be used to search for a path or cycle in a graph, to explore all the vertices of a graph, or to perform other graph-related tasks.
The DFS algorithm works by maintaining a stack of nodes to be visited, starting with the initial node. At each step, the algorithm removes the top node from the stack, visits it, and adds all its unvisited neighbors to the stack. This process continues until the stack is empty, meaning that all nodes in the connected component of the starting node have been visited.
DFS can be implemented recursively or iteratively, and its time complexity depends on the size of the graph and the particular implementation used. In general, DFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
DFS는 깊이 우선 검색(Depth-First Search)의 약자로, 주어진 노드에서 시작하여 역추적 전에 각 분기를 따라 가능한 한 멀리 탐색하는 그래프 트래버설 알고리즘이다. 이 알고리즘은 그래프에서 경로나 사이클을 검색하거나, 그래프의 모든 정점을 탐색하거나, 다른 그래프 관련 작업을 수행하는 데 사용할 수 있다.
DFS 알고리즘은 초기 노드부터 시작하여 방문할 노드의 스택을 유지 관리하는 방식으로 작동합니다. 각 단계에서 알고리즘은 스택에서 최상위 노드를 제거하고, 이 노드를 방문하고, 방문하지 않은 모든 인접 노드를 스택에 추가합니다. 이 프로세스는 스택이 비워질 때까지 계속됩니다. 즉, 시작 노드의 연결된 구성 요소에 있는 모든 노드를 방문했습니다.
DFS는 재귀적으로 또는 반복적으로 구현될 수 있으며, 시간 복잡성은 그래프의 크기와 사용된 특정 구현에 따라 달라진다. 일반적으로 DFS는 O(V + E)의 시간 복잡도를 가지며, 여기서 V는 정점의 수이고 E는 그래프의 모서리의 수이다.
When implementing DFS in code, the typical order of operations is:
- Initialize a visited set or array to keep track of which nodes have been visited.
- Create a stack or use the system call stack to keep track of the nodes to be explored.
- Add the starting node to the stack and mark it as visited.
- While the stack is not empty, pop the top node from the stack.
- For each unvisited neighbor of the popped node, mark it as visited and add it to the stack.
- Repeat steps 4 and 5 until the stack is empty.
코드에서 DFS를 구현할 때 일반적인 작업 순서는 다음과 같다:
방문한 노드를 추적하기 위해 방문한 세트 또는 어레이를 초기화합니다.
스택을 만들거나 시스템 호출 스택을 사용하여 탐색할 노드를 추적합니다.
시작 노드를 스택에 추가하고 방문으로 표시합니다.
스택이 비어 있지 않은 상태에서 스택의 맨 위 노드를 팝합니다.
팝업된 노드의 방문되지 않은 각 인접 노드에 대해 방문됨으로 표시하고 스택에 추가합니다.
스택이 비워질 때까지 4단계와 5단계를 반복합니다.
🔍Approach
DFS - Stack
[ 1, 1, 0 ]
[ 1, 1, 0 ]
[ 0, 0, 1 ]
i번째 computer의 i번째 값은 무조건 1이 되어야 함 (대각성분의 값은 항상 1)
따라서 볼 때 if 문으로 봐야 함
i번째 computer에서 i이외의 인덱스의 값이 0이면 연결이 되지 않은 것이고 1이면 연결되어 있는 것이다.
i행별로의 sum값이 1일 때 anwer+=1 한다. 마지막에 return할 때는 answer에 +1한 값을 return한다.
computers
| i / j | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 |
computers[i][j] == 1 and i != j
stack.append([i,j])
stack
- append할 것: 노드의 인덱스 값
- pop한 값을 방문노드로 지정한다.
- 언제 pop? : 스택의 값이 있으면 pop한다.
- neighbor에 있는 index를 append 이것을 반복 다 볼 때까지 반복함
stack = [0]
visited = [False] * n #방문여부 확인 😀
🚩My submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(n, computers):
answer = 0
visited = [False] * n
stack = []
for i in range(n):
if visited[i] == False:
stack.append(i)
answer += 1
while stack:
i = stack.pop()
visited[i] = True
for j in range(n):
if computers[i][j] == 1 and i != j:
if visited[j] == False:
stack.append(j)
return answer
🚩Others submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(n, computers):
answer = 0
pNode = [False] * n
stack = []
for i in range(n):
if pNode[i] == False:
answer += 1
stack.append(i)
while stack:
value = stack.pop()
pNode[value] = True
for j in range(n):
if j != value and computers[value][j] and not pNode[j]:
stack.append(j)
return answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(n, computers):
answer = 0
pNode = [False] * n
def dfs(node):
nonlocal pNode
nonlocal computers
if pNode[node] == True:
return
pNode[node] = True
for i in range(n):
if pNode[i] == False and computers[node][i]:
dfs(i)
for k in range(n):
if pNode[k] == False:
dfs(k)
answer += 1
return answer