[programmers] 프로그래머스 Level3 네트워크(파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level3 네트워크

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

* 왜 dfs를 이용했을까?

- 일반적으로 노드에서 다음 노드로 넘어갈 노드를 찾기 위한 과정에서 쓰이는 탐색 기법은 dfs/bfs가 있다. 그 중 간선이 하나로 갈 때 경우만 보였기에 dfs를 이용하여 풀이

 

 

 

1) 문제

---

코딩테스트 연습 - 네트워크

 

 

 

 

 

2) 코드

---

def dfs(n, computers, start, visited):
    visited[start] = True
 
    for i in range(0, n):
        if(visited[i]==False and computers[start][i]==1):
            visited = dfs(n, computers, i, visited)
    return visited
        
 
def solution(n, computers):
    visited = [False] * n
    answer = 0
 
    for start in range(0, n):
        if(visited[start] == False):
            dfs(n, computers, start, visited)
            answer += 1
 
    return answer

 

 

 

3) 풀이 과정

---

dfs를 기초적으로 구현만 해보면, 해당 문제는 쉽게 구현이 가능하다.

우선 전체를 [False, False, False.... ] 를 n개로 선언하고 방문 할 때 마다 True 처리를 한다.

 

입출력 예시를 다음과 같이 변환시키면 편하다.

 

computers = [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1]
]

computers2 = [
[1, 1, 0],
[1, 1, 1],
[0, 1, 1]
]

 

위의 정보를 가지고 computers[i][j]를 통해 방문 처리를 해나가고 네트워크의 개수를 설정해주면 된다.

 

 

 

 

 

 

 

 

 

4) 정리 노트

---

-1) 다 풀고 난 뒤 느낀점

: 알고리즘문제는 확실히 bottom - > up 방향으로 학습하는게 맞는것 같다. 즉, 이론 이 후에 문제 풀이로 이어지는 과정이 올바른 학습 방향이라고 생각한다.

 

 

-2) 개념

: 탐색 기법 dfs/bfs