Lv3.(깊이/너비 우선 탐색) 네트워크 - Python

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

프로그래머스

 

과거 작성 코드 

def solution(n, computers):
    visited = [False] * n
    
    def dfs(computers, v, visited):
        # 현재 노드 방문 처리
        visited[v] = True
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in range(n):
            if i == v:
                continue
            if computers[v][i] == 1:
                if not visited[i]:
                    dfs(computers, i, visited)
    answer = 0
    
    for i in range(n):
        if not visited[i] :
            dfs(computers,i,visited)
            answer += 1
    
    
    return answer

 

과거 제출했던 코드가 DFS 이므로 BFS 로 구현해보고자 하였다. 

 

 

제출 코드

 

from collections import deque

def solution(n, computers):
    answer = 0
    
    visited = [False] * n
    
    def bfs(graph, start, visited):
        q = deque([start]) 
        # 처음 부분 방문 처리
        visited[start] = True
        # 큐가 빌때까지 반복
        while q:
            v = q.popleft()
            # print(v, end=" ")
            for i in range(n):
                if i == v:
                    continue
                if computers[v][i] == 1:
                    if not visited[i]:
                        q.append(i)
                        visited[i] = True
            
    for i in range(n):
        if visited[i] == False:
            bfs(computers, i, visited)
            answer += 1
    
    
    return answer

 

bfs는 큐에 넣어줄때 방문 체크를 하는것을 까먹고있었다. 이를 잊지 말도록하자!!

 

 

스터디 인원 창우님 코드 :

 

 

25년 재풀이

 

1. DFS 구현

def solution(n, computers):
    answer = 0
    visit = [False] * n
    
    def dfs(start,visit,computers):
        if not visit[start] : # 방문 안했다면 방문했다고 체크
            visit[start] = True
            for nextnode, cango in enumerate(computers[start]):
                if nextnode != start and cango == 1:
                    dfs(nextnode,visit,computers)
    
    for i in range(n):
        if not visit[i] :
            dfs(i,visit,computers)
            answer+= 1
    
    return answer

원리 자체는 동일한데, 오랜만에 풀어서인지 좀 더 세련되지 못하다. 핵심은 갈수 있는 곳(노드)를 파악해서 DFS로 연결시켜주는것!

 

2. BFS  구현

import collections

def solution(n, computers):
    answer = 0
    q = collections.deque()
    visit = [False] * n
    
    for i in range(n):
        if not visit[i]:
            answer += 1
            
            q.append(i)
            visit[i] = True
            while q:
                cur = q.popleft()
                for j in range(n):
                    if computers[cur][j] == 1 and cur != j and visit[j] == False: # 갈수있는지, 같은노드는 아닌지, 이미 방문했는지 확인
                        q.append(j)
                        visit[j] = True
                        
            
    
    return answer

 

역시나 핵심

DFS 는 현재 노드 True 체크, BFS는 넣을때 True 체크