99클럽 코테 스터디 4일차 TIL(BFS)

📎 문제링크

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

프로그래머스

 

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

BFS 또는 DFS (둘다 해결 가능)

💡 문제 해결 방법

연결되어 있는 노드를 찾으면 되는 문제이다.

1) BFS

빈 graph 배열에 연결된 노드를 추가한다.

그 후 길이 만큼 반복문을 돌면서 만약 노드를 방문하지 않았다면 bfs를 해준다.

bfs 에서는 graph에 속한 노드를 q에 넣어주면서 방문 표시를 해준다.

 

💻 오늘 작성한 코드

from collections import deque
def solution(n, computers):
    answer = 0
    connect = [[] for _ in range(n+1)]
    visited = [False for _ in range(n+1)]
    
    def bfs(node):
        q = deque()
        q.append(node)
        while q:
            N = q.popleft()
            if visited[N]==False and connect[N]!=[]:
                visited[N]=True
                for c in connect[N]:
                    q.append(c)
                    
    for i in range(n):
        for j in range(n):
            if i!=j and computers[i][j]==1:
                connect[i+1].append(j+1)

    for a in range(1,n+1):
        if visited[a]==False:
            bfs(a)
            answer+=1
    return answer

👍 이전에 작성했던 코드

def solution(n, computers):
    answer = 0
    visited = [0]*n #방문 표시 리스트
    def dfs(pc):
        visited[pc]=1
        for i in range(n):
            if visited[i]==0 and computers[pc][i]:
                dfs(i)
    
    for pc in range(n):
        if visited[pc]==0:
            dfs(pc)
            answer+=1
                
    
    return answer

✔ 생각해봐야 할 점

BFS 말고 DFS도 함께 구현해볼 것!