프로그래머스 - 네트워크

(아마) 마지막으로 작성하는 wecode 태그의 게시글.

1. 문제 링크

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

2. 문제풀이 코드 & 해설

1. 내 코드 (리팩토링 이전)

count = 0
def DFS(graph,v,visited) :
    global count
    if visited[v] == 0 :
        return
    
    visited[v] = 0
    count += 1
    
    for i in graph[v] :
        if visited[i] == 1 :
            DFS(graph,i,visited)

def make_cute_graph(computers,n) :
    graph = []
    for i in range(n) :
        graph.append([])
    
    for curr_com_num in range(n) :
        for net_com_num in range(n) :
            if curr_com_num == net_com_num :
                continue
            if computers[curr_com_num][net_com_num] == 1:
                graph[curr_com_num].append(net_com_num)
    return graph

        
def solution(n, computers):
    answer = 0
    visited = [1 for i in range(n)]
    graph = make_cute_graph(computers,n)
    
    for i in range(n) :
        if visited[i] == 1 :
            answer += 1
            DFS(graph,i,visited)

    return answer+n-count

해설 :

1. 처음으로 실행되는 solution 함수에서
   nXn 형태의 매트릭스로 되어있는 데이터를
   나에게 익숙한 형태로 변형한다.

i번째 내부 리스트에 들어있는 숫자들은,
i번 컴퓨터와 연결된 다른 컴퓨터를 의미한다.
모든 내부 리스트는 본인 컴퓨터를 포함하지 않는다.

[
  [1],
  [0, 2],
  [1]
]

2. DFS함수에서, 처음 시작한 컴퓨터에 연결된 모든 컴퓨터를 방문한다.
   방문할 때마다 해당 번호를 방문했다고 체크한다. (1 -> 0)

3. 방문여부를 확인해서, DFS함수에 방문할 때마다 카운트를 추가한다.

2. 내 코드 (리팩토링 후)

def DFS(graph,v,visited) :
    if visited[v] == 0 :
        return
    
    visited[v] = 0
    
    for i in graph[v] :
        if visited[i] == 1 :
            DFS(graph,i,visited)

        
def solution(n, computers):
    answer = 0
    visited = [1 for i in range(n)]
    graph = [[i for i in range(n) if computers[net][i] == 1 and i != net] for net in range(n)]
    
    for i in range(n) :
        if visited[i] == 1 :
            answer += 1
            DFS(graph,i,visited)

    return answer
    

변경점

1. 길고 길게 풀어서 변경한 그래프를 한줄로 변경했다.

2. 불필요했던 count를 삭제하고, 숫자에서 n-count를 빼버렸다.

Best 문제풀이 코드1
-> 최지호 , 조양규 , 하윤아빠 , - , 염기웅 외 94 명 님

해설 :
1. 방문리스트 [0] X N을 만든다.

2. DFS를 선언한다.
   DFS의 구조 :
   a. stack = [시작점] 을 선언한다.
   b. stack 방문 지점이 "0"(미방문상태)인지 확인한다.
   c. stack 방문 지점을 방문상태로 변경한다. (=1)
   d. 현재 방문한 지점과 연결된, 모든 다른 지점들에 대하여
   방문하지 않은 지점을 stack에 추가한다.
   e. stack에 데이터가 들어있는 동안 (while) 계속 반복한다.
   
3. visited 에 방문하지 않은 지점이 있는 동안 (while 0 in visited)
   시작점 숫자를 더해가면서 DFS 호출을 반복한다. DFS를 호출할 때마다 카운트한다.

배운점

1. 드디어 처음으로 해답지를 안보고 BFS/DFS 문제를 풀었다!!

2. 내가 원하는 형태로 매트릭스 -> 그래프로 변경할 때
   앞으로는 좀 더 빠르게 코드를 짤 수 있을 것 같다.

3. graph와 visited를 모두 내가 익숙한 형태로 바꿔는 것이,
   주어진 매트릭스를 모두 방문하지 않아 유리하다고 생각했다.
   for문을 여러번 반복하지 않는 깔끔한 코드를 stack을 사용해서 만들 수 있다는 것을 배웠다.
   (왜인지 모르게, 코드가 작동하는 속도는 내가 좀 더 빠르긴 하지만)