0924 3level

오늘은 9월 24일, 하늘이 푸르고 높으며 날씨마저 기분좋게 하는 하루였다!

오늘 이 날씨가 좋아서, 3단계 한번 더 도전하면 좋을것 같아 한번 더 트라이 해봤다! ㅎㅎ

오늘은 이문제를 푼 답안을, 해설과 함께 좀 나열해보고 싶다.
누가 보겠어, 그냥 끄적거리는거지 헿

우선 설명과 함께한 내가 제출한 코드를 보여주자면,

function solution(n, computers) {
    let visited = Array(n).fill(false); // 컴퓨터들을 아직 안 봤다고 표시해둔 것
    let networkCount = 0; // 네트워크 개수를 세는 변수

    function dfs(i) {
        visited[i] = true; // 이 컴퓨터를 이제 봤다고 체크!
        for (let j = 0; j < n; j++) {
            // i번 컴퓨터와 j번 컴퓨터가 연결되어 있고, j번을 아직 안 봤다면
            if (computers[i][j] === 1 && !visited[j]) {
                dfs(j); // j번 컴퓨터도 친구니까 확인하러 갑니다
            }
        }
    }

    // 모든 컴퓨터를 하나씩 확인해봅니다
    for (let i = 0; i < n; i++) {
        if (!visited[i]) { // 아직 안 본 컴퓨터가 있다면
            networkCount++; // 새로운 네트워크를 발견했으니 개수를 하나 올립니다
            dfs(i); // 이 컴퓨터와 연결된 모든 컴퓨터들을 확인하러 갑니다
        }
    }

    return networkCount; // 총 몇 개의 네트워크인지 결과를 돌려줍니다
}

어떻게 문제를 해결할까?

컴퓨터 그룹 찾기: 각 컴퓨터가 다른 컴퓨터들과 연결되어 있다면, 그 컴퓨터들끼리 하나의 그룹(네트워크)을 형성합니다. 우리는 이 네트워크들이 몇 개인지를 찾고 싶다 (그렇지 않니).

방문한 컴퓨터 체크: 어떤 컴퓨터를 이미 살펴봤는지 표시할 필요가 있음. 한번 살펴본 컴퓨터는 다시 확인하지 않도록 기록해 두자.

연결된 컴퓨터들 찾아가기(탐색): 한 컴퓨터에서 시작해서, 그 컴퓨터와 연결된 모든 컴퓨터들을 찾아가는 방법이 필요합니다. 이때, 우리가 사용하는 방법이 DFS(깊이 우선 탐색)입니다. 쉽게 말하면, 한 컴퓨터에서 출발해 그 컴퓨터와 연결된 모든 친구들을 찾는 것! (이 문제에서 컴퓨터가 친구가 꽤 많은듯 하당).

모든 컴퓨터 확인: 한 컴퓨터 그룹을 다 확인한 후에는, 다른 컴퓨터도 체크해보며 그룹을 찾아야 함. 새로운 그룹을 찾을 때마다 네트워크 개수를 하나씩 증가시키면 된다.

예시 상황

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

이 배열은 컴퓨터 간의 연결 상태

배열의 구조 설명
각 숫자는 컴퓨터 간의 연결을 의미:

1은 연결이 되어 있다는 의미
0은 연결이 안 되어 있다는 의미
여기서 배열은 다음과 같은 규칙을 가지고 있:

computers[i][j]는 i번 컴퓨터와 j번 컴퓨터가 연결되어 있는지 보여줌.
computers[i][i]는 항상 1. (자기 자신은 당연히 연결되어 있으니까.) // 부럽넹

첫 번째 줄: [1, 1, 0]
이건 0번 컴퓨터에 대한 정보.
computers[0][0] = 1: 0번 컴퓨터는 자기 자신과 연결되어 있다.
computers[0][1] = 1: 0번 컴퓨터는 1번 컴퓨터와 연결되어 있다.
computers[0][2] = 0: 0번 컴퓨터는 2번 컴퓨터와 연결되어 있지 않다.

두 번째 줄: [1, 1, 0]
이건 1번 컴퓨터에 대한 정보.
computers[1][0] = 1: 1번 컴퓨터는 0번 컴퓨터와 연결되어 있다.
computers[1][1] = 1: 1번 컴퓨터는 자기 자신과 연결되어 있다.
computers[1][2] = 0: 1번 컴퓨터는 2번 컴퓨터와 연결되어 있지 않다.

세 번째 줄: [0, 0, 1]
이건 2번 컴퓨터에 대한 정보.
computers[2][0] = 0: 2번 컴퓨터는 0번 컴퓨터와 연결되어 있지 않다.
computers[2][1] = 0: 2번 컴퓨터는 1번 컴퓨터와 연결되어 있지 않다.
computers[2][2] = 1: 2번 컴퓨터는 자기 자신과 연결되어 있다.



이 배열을 해석하면
0번 컴퓨터는 1번 컴퓨터와 연결되어 있지만, 2번 컴퓨터와는 연결되어 있지 않다.
1번 컴퓨터도 0번 컴퓨터와 연결되어 있지만, 2번 컴퓨터와는 연결되어 있지 않다.
2번 컴퓨터는 0번과 1번 컴퓨터 모두와 연결되어 있지 않고, 자기 자신과만 연결되어 있다!
이 상황에서 우리는 두 개의 네트워크가 있다고 할 수 있음:

0번과 1번 컴퓨터가 연결된 네트워크
2번 컴퓨터는 혼자만 연결된 네트워크
따라서 네트워크의 개수는 2

이 문제는 "깊이/너비 우선 탐색(DFS/BFS)" 카테고리에 들어있었다! 그래 여기서 의문이 들겠징

DFS란?

DFS는 깊이 우선 탐색(Depth-First Search)의 줄임말. 이 탐색 방법은 그래프나 트리 구조에서 많이 사용되는데, 어떤 한 지점(노드)에서 출발해서 가장 깊이 있는 곳까지 계속 내려가다가 더 이상 갈 곳이 없으면 다시 돌아오는 방식

아 어렵다! 더 쉽게 가보자면,

한 길로 쭉 내려가다가 막다른 길이면 돌아와서 다른 길을 찾아가는 탐색

DFS의 동작 방식

시작점에서 출발: 처음 탐색을 시작하는 곳에서 출발합니다.
갈 수 있는 곳까지 계속 이동: 현재 위치에서 갈 수 있는 곳이 있으면 계속해서 그곳으로 이동합니다. (여기서 '깊이'는 바로 옆에 있는 곳이 아니라 최대한 끝까지 내려가는 걸 의미.)
막다른 길이면 돌아옴: 더 이상 갈 곳이 없으면, 이전 단계로 돌아와서 다른 갈 수 있는 길을 찾습니다.
모든 경로 탐색: 모든 가능한 길을 다 탐색할 때까지 이 과정을 반복합니다.

쉽게 예를 들자면,

트리 구조를 살펴보자.

   1
  / \
 2   3
/ \
4   5

DFS 탐색은 1번에서 시작해서:

1번 → 2번 → 4번 (더 이상 갈 곳이 없으니 2번으로 돌아옴)
2번 → 5번 (더 이상 갈 곳이 없으니 1번으로 돌아옴)
1번 → 3번 (더 이상 갈 곳이 없으니 끝!)

DFS를 어떻게 사용할까?
방문 표시: 한 번 간 곳은 다시 가지 않도록 방문 체크.
재귀 함수로 구현: 재귀적으로 자신과 연결된 곳을 계속 방문.

    visited[node] = true; // 현재 노드를 방문했다고 체크

    for (let nextNode of graph[node]) {
        if (!visited[nextNode]) {
            dfs(nextNode, visited, graph); // 방문하지 않은 연결된 노드로 재귀 호출
        }
    }
} 

그래서, 이문제를 어떻게 푼다고?

네트워크 문제에서 DFS가 어떻게 사용되는지 다시 살펴보면

컴퓨터들이 네트워크로 연결되어 있을 때, 한 컴퓨터에서 출발해서 그 컴퓨터와 연결된 모든 컴퓨터를 찾습니다. DFS는 이 연결된 컴퓨터들을 끝까지 찾아 내려가는 방식으로 탐색하는데, 이 과정에서 이미 방문한 컴퓨터는 다시 보지 않도록 하여 한 네트워크를 완성하게 됩니다.

그래서, 새로운 네트워크를 찾을 때마다 DFS를 이용해 그 네트워크에 속한 모든 컴퓨터를 찾는 방식으로 문제를 해결하는 거임!

느낀점

3단계를 풀었다고? 내가요?
핳 너무 행복하당
매일은,, 어렵겠지 하지만, 한계를 지으면 이겨낼 수 없다.

지금 그냥 뿌듯하다. 내가 해냄.