[알고리즘] DFS - 네트워크(프로그래머스)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43162

문제

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

입출력 예시:

n = 3

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

---

너무 오랜만에 다시 풀기에 for문으로 어케 해볼려다가 실패.

고민을 하다가, 해답을 보고 다시 이해한 후, 다시 혼자서 풀이로 풀었다.

def solution(n, computers):
    answer = 0
    ch = [0 for _ in range(n)]

    def dfs(n, computers, start):
        stack = [start]
        while stack:
            i = stack.pop()
            for j in range(n):
                if ch[j] == 0 and computers[i][j] == 1:
                    ch[j] = 1
                    stack.append(j)

    for i in range(n):
        if ch[i] == 0:
            dfs(n, computers, i)
            answer+=1
        
    return answer

 

언뜻 보면 결국 섬을 구하는 것처럼 보인다.

[[1,1,0],
[1.1.0],
[0,0,1]]

이렇게 되어있으니 뭉쳐있는 왼쪽위 한덩어리랑, 오른쪽아래의 한덩어리 이렇게 두개의 섬이 보이니까
dx,dy 방향을 설정해서 위아래로 인접한 애들이 있는지 확인하는 방법이 있겠다!!라고 생각하면 틀린거다ㅋㅋㅋ 왜냐하면 이러면
[[1,0,1]
[0,1,0]
[1,0,1]] 이 배열을 5개의 섬으로 오해할 것이기 때문이다. 현재 문제는 연결되 네트워크를 구하는 것이기에 2개가 답이다 이것도.

 

 

따라서 지금 내가 작성한 것처럼 풀어야 해야 한다.(나중에 섬문제 다시 풀자 어케 했더라 그건...ㅋㅋㅋ)
암튼 해결한 논리는 다음과 같다.

1. 먼저 체크배열을 n의 길이만큼 만들고 0으로 초기화한다.
2. 0번 컴퓨터에서 시작해보자
3. dfs함수의 while문이 핵심임 들어가보자. 0에서 시작하니까 stack에 0 넣고 시작함
4. j=0일 때, [0,0]에 1이 있고, ch[0]=0이므로 stack에 0추가하고 ch[0]=1로 체크!
5. j=1일 때, [0,1]에 1이 있고, ch[1]=0이므로 stack에 1추가하고 ch[1]=1로 체크!
6. j=2일 때, [0,2]에 1이 없으므로 걍 패스!
7. stack에 지금 0이랑 1 들어있음.
8. 스택 다 빼고 나면, 네트워크에 연결된 애들 돌면서 ch[]에 체크해준거임
9. 이제 바깥 solution함수의 for()문에서 ch[]에 체크해본적 없는애들 있는지 보면서 다시 반복한다.이 때 새로 dfs에 들어갈 때마다 새로운 네트워크에 들어가는 것이므로 answer에 1을 더해준다.

대략 이런데, 지금 스터디카페니까 이따 집가서 다시한번 풀어보쟝