[DFS/BFS] 네트워크 - Java코드

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

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

문제

 

 

설계

노드별 간선의 연결여부가 네트워크수를 결정 짓는다.

Top으로부터 연결된 아이들을 제거해가면서 네트워크수를 Count해주면 될것 같다.

 

나는 computers[i][i]값이 무조건 1이라는 속성을 이용해서 

Flag로 활용하여 이미 연결된 네트워크라는 것을 확인 할때마다 0으로 바꿔주었다.

 

(잘못된) 풀이

class Solution {
	static int ans=0;	
	public static void bfs(int i, int[][] computers) {
		for(int j=i+1;j<computers.length;j++) {
			if(computers[i][j]==1) {
				computers[j][j]=0;
				bfs(j,computers);
			}
		}
		
	}
	public static int solution(int n, int[][] computers) {
		for(int i=0;i<n;i++) {
			if(computers[i][i]==1) {
				ans+=1;
				bfs(i,computers);
			}
		}		
		return ans;
	}
}

연결된 1값을 0으로 셋팅하면서 연결된 노드를 재귀적으로 타고들어가도록 설계하였다.

근데 한가지 간과한것이있다.

순회하는 부분에서 j=i+1로 돌리도록하여

이전에 타고들어온 노드로 돌아가지 않도록 해주려했는데,

 

되려 1-2-4-3 순서로 연결된 네트워크의 경우, 4번에서 3번으로 가지 못하는 케이스가 생긴것이다ㅠ

 

// Error TestCase
	public static void main(String[] args) {
		int n = 4;
		int[][] computers = {{1, 1, 0, 1}, {1, 1, 0, 0},{0, 0, 1, 1}, {1, 0, 1, 1}};
		System.out.println(solution(n, computers));
	}

 

하여 자기 자신만 0으로 바꾸고 들어가지않고, 연결된 값들을 거칠때마다 모두 0으로 바꿔주면서, 

전체 순회하도록 재설계하였다.

 

정답코드

class Solution {
    static int ans=0;       
    public static void bfs(int i, int[][] computers) {
        computers[i][i]=0;
        for(int j=0;j<computers.length;j++) {
            if(computers[i][j]==1) {
                computers[i][j]=0;
                bfs(j,computers);
            }
        }

    }
    public int solution(int n, int[][] computers) {
        for(int i=0;i<n;i++) {
            if(computers[i][i]==1) {
                ans+=1;
                bfs(i,computers);
            }
        }       
        return ans;
    }
}

 

 

문제가 예전보다 빨리빨리 풀려서 기분이 좋다.

비숫한 유형에 문제를 풀어서 그런거지만, 실력향상이라 믿고싶다.