문제 소개

• 코딩테스트 준비를 위해서 프로그래머스 BFS/DFS 문제를 다시풀어보는데 쉽지 않다..
• 전형적인 그래프와 DFS문제이다.

풀이 방법

• 배열을 순차적으로 탐색하면서 값이 1인 값이 있으면 네트워크 수(answer)을 1씩 증가 시켜준다.
• visited라는 방문확인용 리스트를 만들고 마찬가지로 초기에 1이 발견되면 방문 체크를 해준다.
• DFS를 통해서 같은 행 , 그러니깐 노드가 연결되어 있는 간선(값이 1인)은 0으로 바꿔주고 방문하지 않은 노드라면 DFS 탐색을 실시해서 0으로 바꿔준다.

def dfs(i,computers,visited):
    visited[i]=1 # 방문체크한다.
    for j in range(len(computers[0])):
        if computers[i][j] == 1 : # 같은 행에 1이 있으면 
            computers[i][j] = 0 # 0으로 바꿔주고
            if visited[j] ==0: # 열부분이 방문하지 않았다면
                dfs(j,computers,visited) # dfs 탐색
                
                
def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    for i in range(len(computers)):
        for j in range(len(computers[0])):
            if computers[i][j] == 1: #연결되어 있으면
                dfs(i,computers,visited)
                answer+=1 # 네트워크 수 증가
    return answer