programmers. 네트워크 (python)

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

 

 

 

문제를 대충 읽고 삼성st Flood fill 문제구만! 하고 시작했더니 보기좋게 틀려버렸다.

이 문제는 어떤 그래프에서 서로 연결된 클러스터들이 몇 개인지 찾아내는 문제이다.

 

2667번. 단지 번호 붙이기 문제와는 확실히 다른 문제이다. 단지 번호 붙이기 문제는 인접 행렬이 주어지는 게 아니라 단순히 2차원 행렬이 주어지는 것이었다.

하지만 이 문제는 인접 행렬이 주어지는 문제이다. 단지번호붙이기 문제에서는 (0, 0)에서 곧바로 (0, 4)를 방문하지 못하지만 인접 행렬 문제에서는 방문할 수 있다.

인접행렬에서 (0, 4) = 1 이라는건 이런 걸 의미한다.

차이를 말하자면 2차원 배열과 1차원 배열의 차이라고 할까? 사실 이 두 문제는 너무나도 다른데 내가 헷갈린거라 설명할 말도 없다. 

단지번호붙이기에서 주어진 행렬은 각 노드의 위치를 알려준 거지만 (row, col)

이 문제에서의 행렬은 인접행렬이므로 두 노드가 연결되어있는지를 알려준 것이다. (v, next_v)

그래서 visited 배열은 1차원 배열이 되어야 한다. (각 노드에 row, col 위치가 없고 노드 이름만 존재하므로)

 

+ 인접행렬에서 자기 자신으로 향하는 것을 1로 표시한다고 했는데, 이 말은 그래프 탐색을 할 때 자기 자신은 아무 처리하지 않고 일단 방문한 뒤 쓰루한다는 것을 의미한다. 

# 네트워크
def dfs(v, adj, visited):
    for next_v in range(len(adj)):
        if not visited[next_v] and adj[v][next_v]:
            visited[next_v] = 1
            dfs(next_v, adj, visited)


def solution(n, computers):
    answer = 0
    visited = [0 for _ in range(n)]

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

    return answer