[level 3] 네트워크

 문제 

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3 

프로그래머스

 사용 언어 

Python3

 풀이 과정 

앗 이 문제는 첫 번째 제출에서 3개의 테스트 케이스가 실패였다!

이게 틀린 코드인데 q.popleft() 해서 얻은 num에 대한 방문처리가 빠진 것 같았다.

그런데 코드를 다시 보니 방문처리 부분이 불필요하게 겹쳐서 num에 대한 방문처리만 남기고 수정했더니 통과했다.

from collections import deque
from collections import defaultdict 

def bfs(link, visited):
    q = deque([(0)])
    visited[0] = 1
    count = 0
    # 방문하지 않은 노드가 없을 때까지
    while visited.count(0) != 0:
        remain = visited.index(0)
        visited[remain] = 1
        q.append(remain)
        while q:
            num = q.popleft()
            for connect in link[num]:
                if visited[connect] == 0:
                    visited[connect] = 1
                    q.append(connect)
        count += 1
                
    return count

def solution(n, computers):
    visited = [0 for _ in range(n)]
    print(visited)
    link = defaultdict(list)
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i != j:
                link[i].append(j)
    # print(link)
    answer = bfs(link, visited)
    return answer

시간은 나쁘지 않아보이는데 아래서 다른 코드랑 비교!

 

 제출 답안 

from collections import deque
from collections import defaultdict 

def bfs(link, visited):
    q = deque([(0)])
    count = 0
    # 방문하지 않은 노드가 없을 때까지
    while visited.count(0) != 0:
        remain = visited.index(0)
        q.append(remain)
        while q:
            num = q.popleft()
            visited[num] = 1
            for connect in link[num]:
                if visited[connect] == 0:
                    visited[connect] = 1
                    q.append(connect)
        count += 1
                
    return count

def solution(n, computers):
    visited = [0 for _ in range(n)]
    print(visited)
    link = defaultdict(list)
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i != j:
                link[i].append(j)
    # print(link)
    answer = bfs(link, visited)
    return answer

 

 다른 사람 풀이 

똑같은 bfs로 풀이했는데 bfs 함수를 따로 정의하지 않았다고 해도 코드가 훨씬 짧다!

보니깐 내가 defaultdict로 link 관계를 만들어 준 과정을 그냥 deque 안에 넣을 때 if문으로 처리하신 것 같다..?!

 

오늘은 바빠서 넘어가는데(진짜임) 며칠 뒤에 참고해서 내 코드 좀 개선해야겠다.

from collections import deque

def solution(n, computers):
    visit = [False for _ in range(n)]
    que = deque([0])
    ans = 0

    while visit.count(False) != 0:
        node = visit.index(False)
        que.append(node)

        while que:
            visitedNode = que.popleft()
            visit[visitedNode] = True

            for i in range(n):
                if computers[visitedNode][i] != 0 and visit[i] == False:
                    que.append(i)
                    visit[i] = True
        ans += 1
    return (ans)

궁금해서 시간만 체크해봤는데 함수도 하나고 불필요한(?) 연결 관계 그래프를 안만들어서 확실히 조금 더 빠르다.

 

출처: https://velog.io/@sangwoo24/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AClv2BFS