[프로그래머스] 네트워크 (Python)(Java) - DFS/BFS

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

 

 

 

 

접근 방법

인접리스트에서 DFS를 사용하는 문제 !

DFS를 통해 연결되어 있는 부분을 끝까지 가다가, 연결이 끊어진 곳에서 멈춘다. ( answer ++ )

그 후 끊어진 부분 이후에도 연결되어 있는 네트워크가 존재하기 때문에 반복하여 DFS를 몇 사이클을 거쳤는지 count해주면 답이 나올 것이다.

 

❗DFS에서 조건 유의하기

이 문제에서는

1) 방문하지 않고,

2) 1일 때 (연결되어 있을 때)

재귀적으로 DFS를 실행한다 !

 

 

 

 

 

 

코드 구현

1) 실패코드 - 이차원 배열 접근

# 실패 코드
def solution(n, computers):
    visited = [[False for _ in range(n)] for _ in range(n)]
    dxs, dys = [1,0,-1,0],[0,1,0,-1]
    answer = 0

    def can_go(x,y):
        return 0<=x<n  and 0<=y<n and not visited[x][y] and computers[x][y] == 1

    def dfs(x,y):
        visited[x][y] = True
        for dx,dy in zip(dxs,dys):
            new_x,new_y = x+dx, y+dy
            if (can_go(new_x,new_y)):
                dfs(new_x,new_y)

    for i in range(n):
        for j in range(n):
            if(can_go(i,j)):
                dfs(i, j)
                answer+=1

    return answer

print(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

• 무작정 입력 값이 2차원 배열로 들어와 2차원 배열로 접근 - 실패 ..

 

 

 

 

2) 성공코드 - 인접리스트

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

    def dfs(node):
        if visited[node]:
            return
        visited[node] = True
        for i in range(len(computers[node])):
            if(computers[node][i] == 1):
                dfs(i)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer += 1
    return answer

print(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

 

 

 

 

3) 최종 코드 - 자바

    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, n, visited, computers);
                answer++;
            }
        }
        return answer;
    }

    void dfs(int node, int n, boolean[] visited, int[][] computers) {
        visited[node] = true;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && computers[node][i] == 1) {
                dfs(i, n, visited, computers);
            }
        }
    }

• 파이썬이랑 자바랑 함께 공부하려니 자꾸 변수를 넣어주는 걸 까먹는다ㅠㅠㅠㅠ,,,,
• 기억해 !!! 👿 👿 👿 👿 👿 👿 👿 👿 👿 👿 👿 👿 👿

 

 

 

 

 

🌊배우게 된 점

DFS문제를 풀며, 최근 풀었던 문제들은 몽땅 2차원 배열을 이용하는 문제였다 ..

그래서 처음 접근할 때, 이차원 배열로 접근하여 1이 모여있는 구간들을 count했는데 테스트케이스는 통과하지만, 나머지 코드는 모두 오류가 발생하는 대참사가 일어났다

인접행렬과 이차원 배열의 차이를 명확히 이해해야겠다 ! 

 

 

 

 

 

 

 

함께 보면 좋은 포스팅
https://min-jii.tistory.com/47

DFS와 BFS