Jinho Tech

간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고

그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다.

check[i] = 0 -> i 노드 들린 적 없음 -> 탐색 시작

check[i] = 1 -> i 노드 들린 적 있음 -> 탐색 X 

보아하니 백준 실버 4 ~ 실버 2 정도가 프로그래머스 Level 3이랑 비슷한 것 같다.

DFS 풀이

def solution(n, computers):
    def dfs(node):
        if graph[node] and check[node] == 0:
            check[node] = 1
            for n in graph[node]:
                dfs(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            dfs(i)
            ans += 1

    return ans

BFS 풀이

from collections import deque

def solution(n, computers):
    def bfs(node):
        q = deque([node])
        while q:
            node = q.popleft()
            if graph[node] and check[node] == 0:
                check[node] = 1
                for n in graph[node]:
                    q.append(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            bfs(i)
            ans += 1

    return ans