구름톤 챌린지 12일차 - 발전기

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

구름LEVEL

 

import java.util.*;

class House{
		int x;
		int y;
		public House(int i,int j){
			this.x = i;
			this.y = j;
		}
	}

class Main {
	public static int N;
	public static int[][] map;
	public static boolean[][] electricity;
	public static int[] dx = {0,0,-1,1};
	public static int[] dy = {-1,1,0,0};
	public static Queue<House> queue = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		electricity = new boolean[N][N];
		
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				map[i][j] = sc.nextInt();
			}
		}
		
		int answer = 0;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(!electricity[i][j] && map[i][j]==1){
					answer++;
					bfs(i,j);
				}
			}
		}
		
		
		System.out.println(answer);
	}
	
	public static void bfs(int i,int j){
		queue.add(new House(i,j));
		while(!queue.isEmpty()){
			House house = queue.poll();
			for(int k=0;k<4;k++){
				House nexthouse = new House(house.x+dx[k],house.y+dy[k]);
				if(nexthouse.x >=0 && nexthouse.x < N && nexthouse.y>=0 && nexthouse.y<N && !electricity[nexthouse.x][nexthouse.y] && map[nexthouse.x][nexthouse.y]==1){
					queue.add(nexthouse);
					electricity[nexthouse.x][nexthouse.y]=true;
				}
			}
		}
	}
	
	public static void check(int x,int y){
		if(electricity[x][y] || map[x][y]==0){
			return;
		}
		electricity[x][y]=true;
		for(int i=0;i<4;i++){
			int posX = x + dx[i];
			int posY = y + dy[i];
			if(posX >=0 && posX < N && posY >=0 && posY < N){
				check(posX,posY);
			}
		}
	}
}

처음에 dfs 방식으로 풀었었다. 근데 계속해서 런타임에러가 났다. 찾아보니 dfs에서 런타임에러가 나는 이유 중 하나가 재귀를 너무 많이 돌아서라고 했다. 그래서 bfs 방식으로 바꿔서 해보았다.

 

계속해서 생기는 런타임에러에 그만둘뻔 했다