문제
https://school.programmers.co.kr/learn/courses/30/lessons/43162
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
풀이
"""
1. 아이디어
- DFS로 풀기
"""
def solution(n, computers):
answer = 0
def DFS(i):
visited[i] = 1
for com in range(n):
if computers[i][com] and not visited[com]:
DFS(com)
visited = [0 for i in range(len(computers))]
for i in range(n):
if not visited[i]:
DFS(i)
answer += 1
return answer
다른 풀이
from collections import deque
def solution(n, computers):
def BFS(i):
q = deque()
q.append(i)
while q:
i = q.popleft()
visited[i] = 1
for a in range(n):
if computers[i][a] and not visited[a]:
q.append(a)
answer = 0
visited = [0 for i in range(len(computers))]
for i in range(n):
if not visited[i]:
BFS(i)
answer += 1
return answer
설명
방문여부를 체크하면서 dfs 로 풀이해야 겠다는 생각을 했다.
<완전 초기 풀이>
def solution(n, computers):
answer = 0
connect = [[0] * n for _ in range(n)]
for j in range(n):
for i in range(n):
if computers[j][i] == 1 or computers[i][j] == 1:
if i != j:
print(i, j)
answer += 1
return answer
완전 초기 풀이때는 computers의 각 원소들이 1인데, 이때 i와 j가 다를때만을 카운트 해서 정답으로 했었다. 이렇게 답을 제출하니 테스트 케이스 1번은 통과 했으나 2번은 통과하지 못했었다.
- 방문하지 않을 경우에만 dfs 호출
- dfs 함수 호출 시 방문 여부 확인
- dfs 함수 호출하는 반복문 내에서 answer 증가
'Coding Test > Python' 카테고리의 다른 글
| [프로그래머스] 단어 변환 (lv.3) (0) | 2023.08.16 |
|---|---|
| [프로그래머스] 게임 맵 최단거리 (0) | 2023.08.15 |
| [프로그래머스] 타겟 넘버 (lv.2) (0) | 2023.08.10 |
| [프로그래머스] 모음사전 (lv.2) (0) | 2023.08.08 |
| [프로그래머스] 전력망을 둘로 나누기 (lv2) (0) | 2023.08.05 |