프로그래머스 - 네트워크

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

프로그래머스

연결되어 있는 그래프의 덩어리가 몇 개인지 구하는 문제이다.

입력을 받음과 동시에 서로 연결되어 있음을 체크하고 BFS나 DFS로 모든 Node를 방문하면서 갯수를 세어주면 풀 수 있는 기초 문제이다.

 

 

def solution(n, computers):
    answer = 0
    visited = [False] * n
    connected = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                connected[i][j] = True
                connected[j][i] = True

visited -> 방문 여부를 체크할 리스트

connected -> 연결 여부를 체크할 리스트

computers 리스트를 돌며 연결이 되어 있을 경우 connected의 해당 index를 True로 바꿔준다.

ex ) 1번 컴퓨터와 2번 컴퓨터가 연결되어 있다면 connected[0][1]와 connected[1][0]을 True로 바꿔준다.

 

 

def solution(n, computers):
    answer = 0
    visited = [False] * n
    connected = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                connected[i][j] = True
                connected[j][i] = True

    for i in range(n):
        if not visited[i]:
            answer += 1
            visited[i] = True
            q = [i]
            while q:
                c = q[-1]
                for j in range(len(connected[c])):
                    if connected[c][j] and not visited[j]:
                        q.append(j)
                        visited[j] = True
                        break
                else:
                    q.pop()
    return answer

for loop를 돌며 모든 Node에 방문하되, 방문 이력이 없는 Node에만 방문한다.

DFS로 방문을 처리했는데 스택의 변수를 q로 둬버린건 실수다.

stack에서 가장 나중에 들어온 Node를 검사하는데, 이 Node와 연결되어 있는 Node 중 아직 방문하지 않은 Node를 stack에 추가하는 방식으로 DFS를 진행했다.

만약 연결되어 있는 Node가 없거나 모두 방문했을 경우에는 그 Node는 pop으로 제거한다.

 

분리가 되어있지 않다면 DFS의 방문 체크로 한 덩어리로 인식될 것이기 때문에 방문되지 않은 Node를 발견할 때마다 answer에 1을 더해주고, answer를 return한다.

 

 

전체 코드

def solution(n, computers):
    answer = 0
    visited = [False] * n
    connected = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                connected[i][j] = True
                connected[j][i] = True

    for i in range(n):
        if not visited[i]:
            answer += 1
            visited[i] = True
            q = [i]
            while q:
                c = q[-1]
                for j in range(len(connected[c])):
                    if connected[c][j] and not visited[j]:
                        q.append(j)
                        visited[j] = True
                        break
                else:
                    q.pop()
    return answer

 

결과

정확성 테스트

테스트 1 〉	통과 (0.08ms, 10.8MB)
테스트 2 〉	통과 (0.05ms, 10.8MB)
테스트 3 〉	통과 (0.11ms, 10.8MB)
테스트 4 〉	통과 (0.11ms, 10.8MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.34ms, 10.9MB)
테스트 7 〉	통과 (0.07ms, 10.7MB)
테스트 8 〉	통과 (0.27ms, 10.9MB)
테스트 9 〉	통과 (0.18ms, 10.8MB)
테스트 10 〉	통과 (0.18ms, 10.8MB)
테스트 11 〉	통과 (1.14ms, 13.9MB)
테스트 12 〉	통과 (0.88ms, 12.7MB)
테스트 13 〉	통과 (0.46ms, 11MB)