[알고리즘/파이썬] 프로그래머스 - 네트워크

문제

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

프로그래머스

 

풀이

예전에는 DFS로 풀었길래 이번엔 BFS로 풀어봤다. 사실 요렇게 하나의 덩어리를 찾는건 DFS가 뭔가 더 정석인 느낌인데... 새로운 것도 하고 싶어서 ㅎㅎ 그리고 난 원래 BFS를 더 좋아한다. 깊이탐색하다보면 재귀때문에 헷갈린다ㅠ

이 문제는 정말 기초적인 DFS BFS문제라서 두 풀이가 맥락이 비슷~하다. 방문한 노드는 visited를 True로 변경해주고 방문하지 않은 아이들만 탐색하는 방식이다.

 

 

코드

DFS

import sys
sys.setrecursionlimit(10**7)
def solution(n, computers):
    
    def dfs(v,visited):
        visited[v]=1
        for i in range(n):
            if v!=i and computers[v][i]==1 and visited[i]==0:
                dfs(i,visited)
        return visited
                

    visited=[0 for _ in range(n)]
    answer=0
                
    for i in range(n):
        if computers[i].count(1)==1:
                answer+=1
                continue
        for j in range(n):
            if i!=j and computers[i][j]==1 and visited[i]==0:
                visited=dfs(j,visited)
                answer+=1
                
    return answer

 

BFS

from collections import deque
def solution(n, computers):
    answer = 0
    visited = [0 for _ in range(n)]
    def bfs(j):
        q = deque()
        q.append(j)

        while q:
            a = q.popleft()
            visited[a] = 1
            
            for v in range(n):
                if v!=a and computers[a][v] ==1 and visited[v] == 0:
                    q.append(v)
                    visited[v] = 1
                    
    for i in range(n):
        if visited[i] == 0:
            answer += 1
        for j in range(n):
            if i==j:
                continue
            if computers[i][j] == 1 and visited[j] == 0:
                bfs(j)
                
        
    return answer