[programmers] 네트워크

<네트워크>

문제(출처: https://school.programmers.co.kr/learn/courses/30/lessons/43162)

 

 

 

문제 풀이

  - 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