[programmers] 네트워크

코딩 테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS)

---

<네트워크>

문제 설명

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.
예를 들어, 컴퓨터 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입니다.

 

문제 풀이

  - my solution

def visit(i, computers, visited):
    visited[i] = True  # 방문
    for j in range(len(computers)):
        if computers[i][j] == 1 and visited[j] == False:  # 연결 되어있으며 방문한 적인 없다면
            visit(j, computers, visited)

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]  # 초기화
    for i in range(n):
        if visited[i] == False:  # 아직 방문한 적이 없다면
            visit(i, computers, visited)  # 방문
            answer += 1  # 네트워크
    return answer

 

문제를 살펴보고 건드리지도 못한 문제이다. 

깊이/너비 우선 탐색이란 말에서부터 겁을 1차로 먹었으며, 자신이 없었기 때문이다.

 

결국 난 시도조차 하지 못하고 검색에 들어갔다.

항상 dfs, bfs의 정의를 봐도 문제에 적용하기도 어려웠다.

 

다른 사람들의 코드를 보며 조금씩 문제의 해결 방향과 코드의 흐름을 알게 되었고

다시 코드를 구현해보았다.

 

1) visited list_False로 초기화를 통해 방문 여부 check

2) 반복문을 통해 방문 여부 check

   2-1) 방문한 적이 없다면 dfs함수로 이동

   2-2) 네트워크 개수 +1

3) visit 함수

   매개변수) 현재 방문 노드, 연결에 대한 정보, 방문 check list

   3-1) 방문했으므로 True로 변환

   3-2) 반복문을 통해 연결이 되어있으며, 방문한 적이 없다면 visit 함수 호출 

---

생각🤔

 

매번 풀까 말까 하다가 울며 시작한 문제이다.

몇몇 사람들의 코드를 봤지만 비슷한 것도 있고 다른 것도 있었다.

왜 같은 dfs인데 다를까 라는 생각이 아직도 든다.

 

이유도 모르는 것은 아직 내가 dfs를 모르기 때문이 아닐까라고 생각한다

조만간 dfs, bfs를 공부해서 완전한 내 힘으로 이 문제를 다시 풀어볼 것이다.

 

곧 dfs, bfs 완전 정복하기를 🤨

---

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges