[Java] 구름톤 챌린지 3주차 : 발전기

- 문제설명

 

- 해결과정

입력값을 받아 배열을 초기화 시킨 후 모든 배열을 탐색하면서 BFS를 호출한다.

BFS가 중간에 끊긴다면 상하좌우로 이어진 모든 집을 탐색한 것이다. 

이때 count를 증가시키고, 아직 방문하지 않은 나머지 집에 대해서 BFS를 호출하면 된다.

결론적으로 모든 배열을 돌고나면 몇번의 BFS가 호출되었는지 count값으로 확인할 수 있다.

 

- 솔루션

import java.io.*;
import java.util.*;
class Main {
	private static int[][] town;
	private static boolean[][] visited;
	private static int[] dx = {-1, 1, 0, 0};
	private static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		town = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				town[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int result = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(town[i][j] == 1 && !visited[i][j]) {
					bfs(i, j);
					result++;
				}				
			}
		}
		System.out.println(result);
	}
	
	private static void bfs(int curY, int curX) {
		visited[curY][curX] = true;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{curY, curX});
		
		while(!q.isEmpty()) {
			int[] xy = q.poll();
			for(int i = 0; i < 4; i++) {
				int nextX = xy[1] + dy[i];
				int nextY = xy[0] + dx[i];
				try {
					if(town[nextY][nextX] == 1 && !visited[nextY][nextX]) {
						q.add(new int[]{nextY, nextX});
						visited[nextY][nextX] = true;
					}
				} catch (ArrayIndexOutOfBoundsException e) {}
			}
		}
	}
	
	
}