프로그래머스 Lv3 BFS/DFS 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 55분 소요

from collections import deque

def dfs(start,graph,visited,answer):

    stack = deque([start])

    while stack:

        node = stack.pop()

        if not visited[node]:
            stack.extend(graph[node])
            visited[node] = True

    answer += 1
    return answer,visited
    

def solution(n, computers):
    answer = 0

    graph = {i:[] for i in range(1,len(computers[0])+1)}

    for i in range(1,len(computers)+1):
        for j in range(1,len(computers[0])+1):
            if i!=j:
                if computers[i-1][j-1]==1:
                    graph[i].append(j)
    
    visited = [False for i in range(len(computers[0])+1)]

    for i in range(1,n+1):
        if not visited[i]: 
            answer,visited = dfs(i,graph,visited,answer)

    return answer 

BFS/DFS 문제입니다. 연결된 노드들이 1개의 네트워크라고 할 때 전체 네트워크 갯수를 구하는 문제입니다. 주어진 입력값을 기반으로 그래프 구조를 표현하기 위해 dict형태의 graph구조를 만들었습니다. 또한 하나의 네트워크에서 연결된 노드들을 전부 찾기 위해 DFS로 구현하였고 이때, visitied 리스트와 stack구조를 활용하여 구현하였습니다.

[다른 사람의 풀이1]

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 #DFS로 최대한 컴퓨터들을 방문하고 빠져나오게 되면 그것이 하나의 네트워크.
    return answer

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1: #연결된 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

'나의 풀이'와 유사하게 DFS로 구현한 방식입니다. 다른점은 재귀함수로 표현했다는 점입니다.

[다른 사람의 풀이2]

def solution(n, computers):            
    
    def DFS(i):
        visited[i] = 1
        for a in range(n):
            if computers[i][a] and not visited[a]:
                DFS(a)      
                
    answer = 0
    visited = [0 for i in range(len(computers))]
    for i in range(n):
        if not visited[i]:
            DFS(i)
            answer += 1
        
    return answer

재귀함수로 구현한 '다른 사람의 풀이2'와 전체적인 구조는 유사하되 그래프 구조를 따로 dict형태로 표현하지 않았습니다. 2중 리스트 형태의 입력값이 0 혹은 1로 입력되기 때문에 이를 False,True 표현하여 사용하였습니다. 또한 visited 리스트도 0,1로 표현한 풀이로 훨씬 간결한 코드로 해결한 케이스였습니다.

감사합니다.