프로그래머스/ 네트워크 (python)

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

프로그래머스

 

아이디어

• 인접 행렬 방식의 탐색 문제이다.
• 탐색을 시작한 컴퓨터에 연결 된 다른 컴퓨터까지 탐색한다.
• 방문하지 않은 컴퓨터를 만날 때 마다 answer를 +1 한다.

 

어려웠던 점

처음에는 이것이 코딩테스트다 책에 실려있는 음료수 얼려 먹기와 같은 예제로 착각하고 문제를 풀어 시간이 오래 걸렸다.

이렇게 풀어도 테스트 케이스는 맞았으나 제출에서 처참한 결과가 나왔다.

그래서 혼자 인접 행렬을 그려보면서 체크해본 결과 전혀 다른 문제임을 알게 되었다.

기존 내 생각대로 표현하면 이런식으로 2개의 덩어리? 가 나오게 된다.

 

그러나 예제처럼 네트워크로 나타낸다면

위에 영역과는 다르게 모든 컴퓨터가 이어져 있는 모양이 된다.

간단하게 인접 행렬 방식의 dfs를 구현하면 쉽게 접근 할 수 있던걸 기존에 알던 문제에 대입하다보니 이상한 길로 갔다.

 

더 많은 문제를 풀어보면서 특정 유형에만 익숙해지지 않도록 공부가 더 필요하다

 

전체 코드

def dfs(i, n, computers, visited):
    visited[i] = True
    for j in range(len(computers[i])):
        if computers[i][j] == 1 and not visited[j]:
            dfs(j, n, computers, visited)


def solution(n, computers):
    answer = 0
    visited = [False] * n

    for i in range(n):
        if not visited[i]:
            answer += 1
            dfs(i, n, computers, visited)

    return answer