구름톤 챌린지 12일차

문제

https://level.goorm.io/exam/195694/%EB%B0%9C%EC%A0%84%EA%B8%B0/quiz/1

구름LEVEL

 

풀이

문제에서 <<마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다>> 라고 되어있다. 이 문구를 보고 BFS로 풀면 되겠다고 생각했다.

상하좌우 인접한 집 중 하나가 전력을 공급받고 있다는 뜻은 상하좌우로 인접하면 모두 이어져서 하나의 발전기만 설치하면 된다는 뜻이기 때문이다. 

0	1	0
1	0	1
1	1	1

따라서 다음과 같이 집이 있을때 이어진 집이 있다는 것을 확인했을때 2개의 발전기만 설치하면 된다.

따라서 BFS를 이용하여 그룹을 세면 된다.

 

코드

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		int board [][] = new int [n][n];
		
		for(int i=0;i<n;i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++){
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int result = bfs(n, board);
		System.out.println(result);
	}
	
	static int bfs(int n, int board[][]){
		int dx [] = {0, 1, 0, -1};
		int dy [] = {1, 0, -1, 0};
		
		boolean visited [][] = new boolean [n][n];
		Queue<int []> que = new LinkedList<>();
		
		int result = 0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(visited[i][j] || board[i][j] == 0) continue;
				
				que.add(new int[]{i,j});
				visited[i][j] = true;
				result += 1;
				while(!que.isEmpty()){
					int point [] = que.poll();
					for(int t=0;t<4;t++){
						int nx = point[0] + dx[t];
						int ny = point[1] + dy[t];
						
						if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
						if(visited[nx][ny] ||  board[nx][ny] == 0) continue;
						
						que.add(new int [] {nx, ny});
						visited[nx][ny] = true;
					}
					
				}
			}
		}
		return result;
	}
}