[프로그래머스/JAVA] 네트워크

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

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

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

문제 설명

프로그래머스 문제는 약간 이해하기가 힘들다.. 나만 그런가?
연결된 컴퓨터들은 1개의 네트워크로 본다.
총 네트워크의 개수를 반환하세요. 

풀이 방법

BFS가 익숙해서 BFS 로직을 이용하였습니다.
추가된 점은 컴퓨터(노드)를 연결(방문) 한 적이 있는지 확인하는 로직을 추가하였습니다.

1. 한 번도 연결되지 않은 A 컴퓨터를 가져와 다른 컴퓨터와 연결 여부를 확인한다.
     이때 A 컴퓨터는 연결(방문) 체크
2. A 컴퓨터와 연결되었고 한 번도 연결(방문) 하지 않은 컴퓨터를 추가한다.
     추가한 컴퓨터 연결(방문) 체크
3. 추가한 컴퓨터에 대하여 1~2번 로직을 더 이상 연결(방문)할 컴퓨터가 없을 때까지 반복한다.
4. 1~3이 끝나면 하나의 네트워크가 생성

- 1~4번을 모든 컴퓨터를 각각 출발점으로 보고 반복한다. 

삽질했던 부분은 A 컴퓨터에서 출발하는 네트워크만 탐색하여 찾지 못한 테스트 케이스가 존재했습니다.

삽질했던 케이스

내 코드(JAVA)

 

// 자주 풀던 BFS 로직에 탐색체크 로직 추가 풀이
public int solution(int n, int[][] computers) {
    int answer = 0;
    boolean[] visitChecks = new boolean[n];
    Queue<int[]> q = new LinkedList<>();

    // 기존 BFS처럼 ROOT부터 전체 탐색하는게 아니라 각각의 컴퓨터(Node)를 순회해야함
    for(int i=0; i<computers.length; i++) {
        if(visitChecks[i]) continue;

        q.offer(computers[i]);
        visitChecks[i] = true;

        while(!q.isEmpty()) {
            int[] computer = q.poll();

            for(int j=0; j<computer.length; j++) {
                if(!visitChecks[j] && computer[j] == 1) {
                    q.offer(computers[j]);
                    visitChecks[j] = true;
                }
            }
        }
        answer++;
    }

    return answer;
}

다른 사람 코드

 

public int solution(int n, int[][] computers) {
    int answer = 0;
    boolean[] chk = new boolean[n];
    for(int i = 0; i < n; i++) {
    	if(!chk[i]) {
        dfs(computers, chk, i);
        answer++;
        }
    }
	return answer;
}

void dfs(int[][] computers, boolean[] chk, int start) {
    chk[start] = true;
        for(int i = 0; i < computers.length; i++) {
            if(computers[start][i] == 1 && !chk[i]) {
            dfs(computers, chk, i);
        }
    }
}

 

DFS를 활용한 풀이입니다.

DFS의 개념 및 흐름을 좀 더 학습 후 DFS 방법으로 풀어보는 것도 좋을 것 같습니다.