네트워크

접근 방식

다양한 접근 방식을 시도했다..ㅎ 계속해서 두개의 테스트케이스만 통과하길래 질문하기란에서 어떤 감사한 분이 반례를 올려주신 걸 보고 깨달음.

처음에는 dfs로 주어진 그래프의 1을 추적해서 푸는 방식으로 했는데 그러면 아래와 같은 케이스에서 실패할 수밖에 없다:
[[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]

그래서 따로 그래프로 만들어서 그걸 dfs로 순회하는 방식으로 접근하기로 했다.
이런 식으로:

코드

def dfs(x, graph, visited):
    if visited[x] == True:
        return
    visited[x] = True
    for val in graph[x]:
        dfs(val, graph, visited)

def make_graph(n, matrix):
    graph = dict()
    for i in range(n):
        graph[i] = []
        for j in range(n):
            if i != j and matrix[i][j] == 1:
                graph[i].append(j)
    return graph

def solution(n, computers):
    graph = make_graph(n, computers)
    cnt = 0
    visited = [False] * n
    for x in graph:
        if visited[x] == False:
            dfs(x, graph, visited)
            cnt += 1
    return cnt

✅ UPDATED - 12.07

...??????????

과거의 나 왜 이렇게 풀었지?

주어진 adjacency matrix를 활용하면 쉽게 풀 수 있는 문제다.

computers[x][y]는 x 노드 -> y 노드, y 노드 -> x 노드 양방향 연결 관계가 공통적으로 1로 표현되기 때문에, 어느 걸 먼저 접근해도 상관없이 처리할 수 있다.

주어진 computers를 활용해 DFS 순회하도록 풀이를 업뎃했다.

코드

def dfs(x, n, computers, visited):
    visited[x] = True

    for y in range(n):
        if y == x:
            continue
        if computers[x][y] == 1 and not visited[y]:
            dfs(y, n, computers, visited)


def solution(n, computers):
    visited = [False] * n

    count = 0
    for x in range(n):
        if not visited[x]:
            dfs(x, n, computers, visited)
            count += 1

    return count