프로그래머스 네트워크 (파이썬)

Level 3, DFS/BFS

 

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

코딩테스트 연습 - 네트워크

 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태

컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결 > 컴퓨터 A와 컴퓨터 C도 간접적으로 연결된 하나의 네트워크

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수 반환

 

제한사항

• 1 <= 컴퓨터 수, n <= 200, 자연수
• 0 <= 컴퓨터 번호 <= n-1
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j] = 1
• computer[i][i]는 항상 1

입출력의 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

첫번째 풀이 (오답)

from collections import deque

def BFS(x, y, n, computers, visited):
    q = deque([])
    q.append([x,y])
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in (0,1), (1,0), (0,-1), (-1,0):
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
                continue
            if computers[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = 1
    return visited

def solution(n, computers):
    answer = n
    visited = [[0] * n for _ in range(n)] 
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and computers[i][j]:
                visited = BFS(i, j, n, computers, visited)
                answer += 1

    return answer

computers에서 상하좌우로 이어져 있으면 1개를 출력하는 BFS로 짰는데 이렇게 풀게 되면 한 칸 건너 연결된 네트워크를 찾을 수 없었습니다.

즉,

n = 4,

computers = [[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]

의 반례는 찾을 수 없었습니다.

문제의 풀이 자체가 완전 잘못 되어 다시 풀었습니다.

 

두번째 풀이 (정답)

def solution(n, computers):
    answer = n
    visited = [0] * n 
    Linked = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j] == 0:
                continue
            Linked[i].append(j)
    
    for i in range(n):
        q = Linked[i][:]
        while q:
            adj = q.pop(0)
            if adj <= i:
                continue
            if visited[adj]:
                continue
            answer -= 1
            q = q + Linked[adj]
            visited[adj] = 1
            
    return answer

자기 자신과 연결된 컴퓨터를 1차원 큐(엄밀히 말하면 리스트)에 넣어 가장 가까운 컴퓨터 부터 탐색하게 만들었습니다.

정답은 최대 n개의 네트워크를 가질 수 있 는데 만약 큐에 연결된 또 다른 Link 리스트를 추가한다면 연결되어있다고 판단하여 answer를 1개씩 깍아주었습니다.

단, 인접한 컴퓨터 번호가 자기 자신보다 클 때만 넣어 주어 에러를 잡았습니다.