문제링크
https://programmers.co.kr/learn/courses/30/lessons/43162
문제
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
컴퓨터의 개수 n은 1 이상 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분류
-
알고리즘 분류
깊이/너비 우선 탐색(DFS/BFS) -
난이도
프로그래머스 Level 3 -
사용 언어
python
try 1
dfs를 활용한 visited리스트
연결된 하나의 네트워크들을 재귀호출 DFS를 통해 모두 방문해서 체크하고,
하나의 네트워크 방문이 끝나면 네트워크의 개수를추가 이후 반복 진행
코드
def solution(n, computers):
answer = 0
visited = [False for i in range(n)]
# 방문해야될 컴퓨터
for i in range(n):
if(not visited[i]):
dfs(computers, i, visited)
# dfs를 통해 방문된 네트워크들은 모두 하나의 네트워크라서
answer += 1
return answer
def dfs(computers, target, visited):
visited[target] = True
for i in range(len(computers)):
# 동일한 컴퓨터가 아니면서 연결되어있는 컴퓨터라면
if((i != target) and (computers[target][i])):
# 연결 표시또한 하지않았다면
if(not visited[i]):
# 재귀호출을 통해 모두 방문을 표시
dfs(computers, i, visited)
결과
채점 결과
정확성: 100.0
합계: 100.0 / 100.0걸린시간
3시간
마치며
초반에 노드들의 번호에 신경쓰며 네트워크에 연결된 컴퓨터들에 신경을 쓰면서 이를 합치고 조작하는데 시간이 오래걸렸다.
다르게 접근하도록 문제를 다시 읽었는데 문제의 요구사항이 네트워크의 개수에 초점이 되어있었기에 따로 변형하지 않고 방문리스트만을 두어 체크하여 문제를 풀 수 있게 되었다.
문제의 목적을 더 정확히 이해하고 풀기위한 연습을 추가로 해야겠다.
