[프로그래머스] 네트워크

첫 시도에서 문제를 완전 잘못 이해했었다.

😇 1차 시도

from collections import deque

def bfs(dq, n, computers):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while dq:
        y, x = dq.popleft()
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if computers[ny][nx] == 1:
                dq.append((ny, nx))
                computers[ny][nx] = 0
                
def solution(n, computers):
    answer = 0
    for j in range(n):
        for i in range(n):
            if computers[j][i] == 1:
                answer += 1
                dq = deque([(j, i)])
                bfs(dq, n, computers)

    return answer

computers의 위치를 나타낸게 아니라 연결 관계를 나타낸 그래프이기 때문에 위의 풀이는 당연히 fail.

그렇다면 연결 관계를 나타내는 그래프가 나왔을 때 bfs를 어떻게 사용해야할까?
연결되는 개체를 array로 담아두고 각각의 개체 computer에 연결된 개체 connect를 T/F로 나타내면 연결 유무를 알 수 있다.
그래프보다 낯설지만 사실 더 간단한 로직으로 해결할 수 있다.
좀 더 구체적으로는 0번째 컴과 연결된 컴을 T로 바꿔주고 연결된 컴의 인덱스를 큐에 담아두고, 연결된 컴에 대해서 같은 방법으로 연결된 컴들을 찾아서 T로 바꿔주면 네트워크로 연결된 그룹을 찾을 수 있다.

🤗 2차 시도

BFS 풀이

from collections import deque

def BFS(dq, n, computers, visited):
    while dq:
        current = dq.popleft()
        for connect in range(n):
            if visited[connect] == False and computers[current][connect] == 1:
                visited[connect] = True
                dq.append(connect)

                
def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    dq = deque([0])
    
    for idx in range(n):
        if not visited[idx]:
            dq.append(idx)
            BFS(dq, n, computers, visited)
            answer += 1
            
    return answer

새로운 방법도 있다. 과거의 나는 Union-Find로 풀었더라..ㅎㅎㅎ

Union-Find 풀이

def find_parent(parents, x):
    if parents[x] != x:
        parents[x] = find_parent(parents, parents[x])
    return parents[x]

def union_parent(parents, a, b):
    a = find_parent(parents, a)
    b = find_parent(parents, b)
    if a > b:
        parents[a] = b
    else:
        parents[b] = a

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

    for i in range(n):
        parents[i] = i

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                union_parent(parents, i, j)

    for i in range(n):
        find_parent(parents, i)

    count = 0
    tmp = -1
    for p in parents:
        if p != tmp:
            tmp = p
            count += 1
    return count