[Python : 프로그래머스] 네트워크

문제

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

풀이

DFS로 경로가 몇 개인지 찾는 문제
보통 DFS가 무한루프에 빠지지 않도록 방문내역을 확인하는데,
모든 노드에 대해서 방문기록이 있는지 확인하고, 없으면 DFS 진행시키면서
경로개수를 증가시켜서 해결한다.

def DFS(i, visited, computers) :
    visited[i] = 1       # 방문기록 작성
    for com in range(len(computers)) :
        if computers[i][com] and not visited[com] : 
        # 다른 노드와 이어지는 길이 존재하고, 해당 노드를 방문한 기록이 없다면 
            DFS(com, visited, computers)

def solution(n, computers):
    visited = {i:0 for i, v in enumerate(computers)}
    answer = 0
    for com in range(len(computers)) :
        # DFS 재귀를 다 돌고 나왔는데도 방문기록이 없다면 새로운 경로
        if not visited[com] :
            DFS(com, visited, computers)
            answer += 1

    return answer

재귀 DFS로 풀었다.
파이썬으로 재귀 DFS를 작성해본적이 없음에도 어찌어찌 해냈다.
visited를 해시로 풀어낸게 자랑이라면 자랑.

다른 사람들의 풀이는 다양했으나, 대부분은 DFS.
크게 “와 대박!” 하는 풀이는 없었다.

간혹 3중 for문으로 풀어낸 문제들도 보였는데,
코드는 짧았으나 n이 커지면 n^2을 넘어갈 것처럼 생겼었다.
확실히 이런류 문제는 독창적인 발상보다는 교과서적인 풀이가 대부분인 것 같다.

재귀 DFS 눈 감고도 짤 수 있을만큼 연습하자.