[프로그래머스 Lv3.] 네트워크(python)

1. 문제

문제 설명

제한사항

입출력 예시

입출력 예 설명

---

2. 풀이 과정

내가 생각한 진행 과정

• 우선 n개의 지점을 다 돌아야하기 때문에 지났는지 확인하는 visit을 만든다
• n을 돌면서 아직 지나지 않은 곳(i=0)을 기준으로 deque에 넣고 bfs 진행
  • visit을 1로 변경(지나갔다는 표시)
  • q에 넣고 bfs 진행
    • while q:에서 computer로 값을 빼낸 후에 n개를 돌면서 computer와 index가 다르면서(computer[i][i]는 항상 1이기 때문) 연결되어있고, 아직 방문하지 않았다면 q에 넣고 visit 표시
  • 진행할 때 아직 지나지 않은 곳들만 맨 처음 if문을 통과할 수 있으므로 맨 처음 if문을 통과했다면 answer += 1 시켜주기

최종 코드

from collections import deque

def solution(n, computers):
    visit = [0 for _ in range(n)]
    answer = 0
    for i in range(n):
        if visit[i] == 0:
            answer += 1
            visit[i] = 1
            q = deque([])
            q.append(i)

            while q:
                computer = q.popleft()
                for j in range(n):
                    if j != computer and computers[computer][j] == 1 and visit[j] == 0:
                        q.append(j)
                        visit[j] = 1

    return answer