[프로그래머스] Lv3. 네트워크(Python)

문제 링크

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

풀이 시간

약 23분

접근 방식

DFS로 풀었다.

0번 인덱스 컴퓨터부터 탐색을 시작해서, 방문하지 않았고 현재 컴퓨터와 연결된 컴퓨터라면

→ 다시 dfs 함수를 호출해줬다.

이렇게 되면 마지막 dfs가 리턴될때는 같은 네트워크로 연결된 컴퓨터들을 모두 순회할수 있다.

그래서 dfs 한번이 끝나면 네트워크 1개를 발견한 것이 되므로 answer에 1을 더해줬다.

→ 문제 첫번째 예제에서는 0-1 방문하고 dfs(0)이 끝날 것이다. 그다음에 방문하지 않은 dfs(2) 실행.

정답 코드

1) 재귀함수로 dfs 구현

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    def dfs(curIdx):
        visited[curIdx] = True
        for i in range(n):
            if not visited[i] and computers[curIdx][i] == 1:
                dfs(i)
        
        
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer += 1
    return answer

3) 스택으로 dfs 구현

연습할겸(?) 스택으로도 풀어봤다!

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    def dfs(start):
        stack = deque()
        stack.append(start)
        
        while stack:
            curNode = stack.pop()
            visited[curNode] = True
            for i in range(n):
                if not visited[i] and computers[curNode][i] == 1:
                    stack.append(i)
        
        
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer += 1
    return answer

Thinking 👀

BFS 사용한 풀이

현재 컴퓨터와 인접해있고, 방문하지 않은 모든 컴퓨터들을 queue에 넣어주며 bfs 탐색.

from collections import deque
def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    def bfs(curIdx):
        queue = deque()
        queue.append(curIdx)
        while queue:
            curIdx = queue.popleft()
            visited[curIdx] = True
            for i in range(n):
                if not visited[i] and computers[curIdx][i] == 1:
                    queue.append(i)
        
        
    for i in range(n):
        if not visited[i]:
            bfs(i)
            answer += 1
            
    return answer