📌 프로그래머스 - 네트워크

딱봐도 DFS가 생각나는 문제!
언젠가 BFS로 풀어보고 싶긴 하다.

<내 답안>

def solution(n, computers):
    answer = 0
    visit = [0]*n
    def dfs(x,visit):
        visit[x] = 1
        for j in range(n):
            if j != x and computers[x][j] == 1 and visit[j] == 0:
                dfs(j,visit)
    for i in range(n):
        if visit[i] == 0:
            dfs(i,visit)
            answer+=1
    return answer

<답안 해석>
연결된 노드의 갯수를 구하는 것이 아니라, 연결된 노드끼리 한 묶음(한 개)임을 유의해서 풀면 된다.
(즉, 한 번의 연결에서 연결되어있는 노드를 모두 방문처리 해주면 쉽게 구하기 가능)

def solution(n, computers):
    answer = 0
    # 방문 표시할 변수
    visit = [0]*n

    # dfs 구현
    def dfs(x,visit):
        visit[x] = 1
        for j in range(n):
            if j != x and computers[x][j] == 1 and visit[j] == 0:
                dfs(j,visit)

    for i in range(n):
        if visit[i] == 0:
            dfs(i,visit)
            answer+=1

    return answer

<예제 1 탐색 알고리즘>

예제 1처럼 [[1,1,0],[1,1,0],[0,0,1]] 로 노드가 연결되어 있을 때

visit = [0, 0, 0]

첫 번째 노드부터 탐색 시작,
우선 첫 번째 노드 방문 처리 visit = [1, 0, 0]

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

두 번째 노드랑 연결되어 있으니 두 번재 노드 방문 처리 visit = [1, 1, 0]

이제 더 이상 방문하지 않았고, 연결되어있는(==1) 노드가 없으므로 answer +1 해주고 다음 노드 탐색

하지만 두 번째 노드는 이미 방문처리(visit = [1, 1, 0]이므로.) 되어 있어서 다음 노드를 탐색.

세 번째 노드는 방문하지 않았으므로 세 번째 노드 탐색
[[1,1,0],[1,1,0],[0,0,1]]

자기 자신이 아니고, 연결되어 있으며(==1), 방문하지 않은 노드가 없으므로 종료, answer +1

최종적으로 answer = 2 가 도출되며 정답!

이건 dfs 함수를 밖으로 빼본 답안..
확실이 내부에서 쓸 때보다 따로 모듈로 빼서 돌리면 더 느린 것 같기도..

하지만 코드를 보기 더 직관적이고 깔끔해보인다.

<내 답안2>

def dfs(n,computers,x,visit):
    visit[x] = 1
    for i in range(n):
        if i != x and computers[x][i] == 1 and visit[i] == 0:
            dfs(n,computers,i,visit)
def solution(n, computers):
    answer = 0
    visit = [0]*n
    for i in range(n):
        if visit[i] == 0:
            dfs(n,computers,i,visit)
            answer+=1
    return answer