[DFS] 프로그래머스 고득점킷 네트워크 - Python 파이썬

 

생각하기

연결되어 있는 노드들의 뭉치를 찾는 것이기 떄문에 깊이 우선 탐색을 솔루션 알고리즘으로 생각했다

한개의 노드를 찾으면 연결되어 있는 노드를 타고 다음 연결되어 있는 노드로 흘러가듯이 타고 내려가는 방법이다

 

구현하기

• visited 배열을 통해 한번 방문한 노드는 다시 방문했을 때 더이상 로직을 진행할 필요가 없도록 한다
• computers 배열의 모든 부분을 돌면서 visited를 검사하며 DFS 알고리즘을 실행한다

장애물 사항

• computers 배열에서 row와 col이 같은 것은 결국 자기 자신이니까 for 문을 돌때 생략해도 된다고 생각했다.

하지만 생각하지 못한 예외가 있다

아무 노드랑 연결되지 않은 홀로 있는 노드다! 이런 경우 네트워크로 확인할 수 없기 때문에 row==col 인 것도 포함시킨다

어차피 VIsited를 통해서 방문 처리 된다면 재방문하지 않는다.

 

def dfs(i, n, computers):
    global network, visited
    for j in range(0, n):
        if visited[i][j] != True and computers[i][j] == 1:
            visited[i][j] =True
            dfs(j, n, computers)
    return

def solution(n, computers):
    global network, visited
    #Visited 생성
    visited = [[False]*n for i in range(0, n)]
    
    network = 0
    
    #DFS 진행 첫번째부터 진행해서 
    for i in range(0, n):
        for j in range(0, n):
            if visited[i][j] != True and computers[i][j] == 1:
                visited[i][j] = True
                dfs(j, n, computers)
                network+=1
    
    return network

 

queue를 사용해서 푸는 방법도 있어서 아이디어만 가져와서 한번 코드를 짜봤다

1. visited를 1차원 배열로 만들어서 각 노드의 방문 현황을 체크
2. 방문하지 않은 노드를 큐에 넣기
3. visited가 모두 TRue가 될 때까지 작업을 반복

작업

1. 큐에서 하나를 pop해서 해당 노드에 연결된 노드들을 큐에 넣는다
2. 큐에 넣는 노드들은 VIsited == False 이고 conputers 배열에서 연결성이 확인된 노드들이다
3. 큐에 아무것도 없을 때까지 반복하고 아무것도 없다면 network 개수를 1증가 시킨다

def solution(n, computers):
    # network 수 0으로 초기화
    network = 0
    # 방문 상태 확인
    visited = [False for i in range(n)]
    # queue 생성
    queue = []
    
    while False in visited:
        print(visited.index(False))
        # 아직 방문하지 않은 임의의 index를 QUEUE에 추가
        queue.append(visited.index(False))
        #모든 노드를 방문할 때까지 반복
        while len(queue) != 0:
            idx = queue.pop()
            visited[idx] = True
            print(idx)
            for i in range(0, n):
                if i==idx:
                    continue
                if computers[idx][i] == 1 and visited[i] == False:
                    queue.append(i)
                    visited[i] = True
        network +=1
            
        
    return network