[프로그래머스 #level3] 네트워크.java

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

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

DFS 와 BFS 두 가지로 문제를 해결해 봤다.

 

BFS

package eun;

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		int[][] computers  = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		int n = 3;
		solution(n, computers);
	}
	
	public static int solution(int n, int[][] computers) {
		int answer = 0;
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[n];
		
		// 시작점 for 문
		for (int i=0; i<n; i++) {
			if (!visited[i]) {
				q.add(i);
				
				while(!q.isEmpty()) {
					int cur = q.poll();
					visited[cur] = true;
					
					// 시작점에서 갈 수 있는곳 탐색
					for (int j=0; j<n; j++) {
						if(!visited[j] && computers[cur][j] == 1) q.add(j);
					}
				}
				
				answer++;
			}
		}
		System.out.println(answer);
		return answer;
    }
}

 

DFS

package eun;

public class Eun {
	public static int answer =0;
	public static int[] dx = { 0, 1, 0, -1 };
	public static int[] dy = { 1, 0, -1, 0 };
	public static void main(String[] args) {
		int[][] computers  = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		//int[][] computers  = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
		int n = 3;
		
		solution(n, computers);
	}
	
	public static int solution(int n, int[][] computers) {
		
        for(int y=0; y<n; y++) {
        	for(int x=0; x<n; x++) {
        		if(computers[y][x] == 1) {
        			dfs(x, y, computers, n);
        			answer++;
        		}
        	}
        }
        System.out.println(answer);
		return answer;
    }
	
	public static void dfs(int x, int y, int[][] computers, int n) {
		computers[y][x] = 0;
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (computers[ny][nx] == 0) continue;
			dfs(nx, ny, computers, n);
		}
	}
	
}