프로그래머스 레벨3 네트워크 (JAVA) (DFS,BFS)

 

DFS ,BFS 부셔버리겠다..진짜 처음에 너무 어려웠다..

 

이번 주말에는 BFS , DFS 이론을 보며.. 예제를 보며 공부를 하였다..

 

그리고 도전한 DFS , BFS 문제..

 

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

코딩테스트 연습 - 네트워크

 

레벨 2도 아니고 레벨 3부터 도전하다니 간도 크다..

 

이 문제를 푸는데 하루가 지났다..

 

내가 BFS, DFS 이론만 간단하게 보고 이해하려니

 

당연히 안되었던 거 문제의 이해는 쉽게 하였지만

 

구현을 어떻게 해야 할지 모르겠었다

 

그래서 유튜브 영상을 많이 보고 문제를 결국 풀었다..!

 

https://www.youtube.com/watch?v=_hxFgg7TLZQ 

 

여기 유튜브가 정말 이해하기 쉽게 설명해 주신다..

 

나처럼 BFS, DFS 가 어려운 사람은 한번 보는 게 좋을 거 같다.

 

이 문제는 양방향 그래프다..

 

일단 코드를 보자.

 

모든 코드는 GitHub 에 올려놓았다.

 

 

DFS

public class solution {
  
  private int[][] netWork;
  private boolean[] visited;
  
  public int solution(int n, int[][] computers) {

        int answer = 0;

        netWork = computers;
        visited = new  boolean[n];

        for(int i=0; i<n; i++) {
            if(!visited[i]) { // n 번쟤 컴퓨터에 방문한 기록이 없으면 true 로 dfs 실행
                dfs(i);
                answer++; // 컴퓨터에 방문을 안했따는건 연결이 안되어있다는 뜻 ++; 해줌
            }
        }
        return answer;
    }

    public boolean dfs(int x) { // 컴퓨터가 들어옴

        visited[x] = true; // 컴퓨터 방문표시

        netWork[x][x] = 0; // 자기 자신은 0 처리해줌 대각선기준 본인 0 0 , 1,1 2,2

        for(int i=0; i<netWork[x].length; i++) { // 우측으로 탐색시작. i 가 컴터임
            if(netWork[x][i] == 1 && !visited[i]) {  // ex 0,1 , 이 1인지 방문안했는지와 ,  컴퓨터가 방문했떤 기록이 있는지
                netWork[x][i] = 0; // 처음이라면 0으로 바꿔주고
                dfs(i); // 1번 컴퓨터부터 dfs 탐색시작
            } else {
                netWork[x][i] = 0; // ex) 1번 컴퓨터에 처음방문한게 아니라면 요부분만 방문처리로 0으로 바꿔줌
            }
        }

        return true;
    }
  
}

BFS

public class solution {
  
    public static int solution2(int n, int[][] computers) {

        int answer = 0;

        boolean[] visited = new boolean[n];

        Queue<Integer> queue = new LinkedList<>();

        for(int i=0; i<n; i++) { // 0부터 탐색시작
            queue.add(i);

            if(!visited[i]) {
                answer++;
            }
            while (!queue.isEmpty()) {

                int x = queue.poll();

                visited[x] = true;

                //자기자신 방문처리
                computers[x][x] = 0;

                for(int j=0; j<computers[x].length; j++) { // 관련된걸 싹다~ 방문처리시킨다.
                    if(computers[x][j] == 1 && !visited[j]) { // 처음방문이면 에 방문했던 기록이 없으면
                        computers[x][j] = 0; //방문처리
                        queue.add(j); // 한번더 순회하게 넣어줌
                    } else {
                        computers[x][j] = 0; //방문철.

                    }

                }

            }

        }

        return answer;
    }
}

 

 

 

BFS, DFS 둘 다 한번 탐색한 노드를 방문 처리해주고

 

이미 방문한 노드고 네트워크의 값이 1일 경우에는 

 

0으로 방문 처리해주었다..

 

그리고 매번 새로운 노드를 방문했을 경우에만

 

네트워크의 값을 올려주었다.

 

0,0 1,1 같은 경우가 컴퓨터고 대각선만 잘라서 보았을 때 연결점이다

 

그래서 방문을 확인해주고 반대편에서 카운트를 못 올리게 boolean으로 체크해주어야 한다.

---

(DFS 기준 설명 )

 

예시 문제를 하나 들어보겠다

 

프로그래머스에 있는 첫 번째 입출력 예이다.

 

{1,1,0},

{1,1,0},

{0,0,1}

 

이런 형태의 네트워크 연결이 있다면

 

private boolean[] visited = new boolean[n]; // 컴퓨터 방문 값을 초기 설정해준다.

 

이제 solution에서 for 문을 돈다 i가 시작 값이 0이고

 

if(!visited[i])  n 번째 컴퓨터에 방문한 기록이 없으면 true로 dfs 실행 

첫 i는 0일 것이다

 

        visited[x] = true; // 컴퓨터 방문 표시

        netWork[x][x] = 0; // 자기 자신은 0 처리해줌 대각선 기준 본인 0 0 , 1,1 2,2

 

자기 자신과 컴퓨터를 방문처리해준다.

 

        
     public boolean dfs(int x) { // 컴퓨터가 들어옴

        visited[x] = true; // 컴퓨터 방문표시

        netWork[x][x] = 0; // 자기 자신은 0 처리해줌 대각선기준 본인 0 0 , 1,1 2,2

   	for(int i=0; i<netWork[x].length; i++) { // 0번쨰 컴퓨터부터 -> 방향으로 탐색을 시작한다.
            if(netWork[x][i] == 1 && !visited[i]) { // 처음 0번컴퓨터는 자신은 이미 탐색이 완료 되어있다.
                netWork[x][i] = 0; 
                dfs(i); 
            } else {
                netWork[x][i] = 0; 
            }
        }

        return true;
    }

 

주석으로 해 논거와 같이 처음 0,0 은 이미 dfs를 방문하면서

 

true, 0 방문 처리가 되어서 바로

 

0,1로 이동한다.

 

그럼 0,1 은 == 1이고 visited[1] 번째는 false 이므로

 

dfs 재귀 함수가 다시 실행된다

 

그럼 노드로 들어온 x값은

 

1이고 1번 컴퓨터가 방문처리 되게 된다.

 

다시 정리를 해보자면

 

{1,1,0},

{1,1,0},

{0,0,1}

 

x = 0 번째 컴퓨터일 때 순서대로 0,0 -> 0,1 -> 1,0 -> 1,1 이렇게 방문을 하게 된다

 

solution에서 0번째에 컴퓨터가 실행될 때 1번까지 전부 방문을 하고

 

answer++; 네트워크 값을 올린다

 

두 번째 for문에서 1이 오지만 1은 이미 visited에서 true로 방문처리가 되어있어 dfs를 호출하지 않고

 

새로운 미 방문 컴퓨터가 왔을 시 연관된 모든 컴퓨터를 방문 처리하고

 

answer 값을 올려주는 방식이다..

 

---

글을 쓰면서 느끼지만 설명하기가 정말 어려운 거 같다.

 

코드만 달랑 올리고 싶지는 않고 설명을 하고 싶은데 깔끔하게 정리하기가 힘든 거 같다..

 

더욱 노력해야겠다..

 

 

 

BFS와 DFS의 상세한 설명을 다음 주 내로 따로 정리해서 올릴 예정이다.

 

여기에 쓰기에는 양이 많은 거 같다.

 

BFS DFS 한번 해보니까 익숙해지는 거 같다....