[구름톤 챌린지] Day12 발전기 (Java)

문제 설명

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 n인 정사각형 모양의 마을을 만들고 있다.

각 행열에는 숫자 0 또는 1이 적혀 있고, 그 숫자가 의미하는 바는 아래와 같다.

0: 아무것도 없는 칸

1: 집이 있는 칸

 

마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다.

플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 구해보자.

 

구름LEVEL

전체 코드는 맨 마지막에 있습니다.

---

문제 예시)

예를 들어, n=5이고 다음과 같은 마을이 주어진다고 가정합시다.

 

발전기가 한 집에 있다면 그 집과 상하좌우로 연결된 모든 집들은 다 전력을 공급받는다는 뜻입니다.

---

 T I P 

• 마을의 행과 열을 차례대로 돌면서 1을 만나면, 그 집과 상하좌우로 연결된 모든 집들을 탐색해 줍니다.
• 방문한 집들은 다시 방문하지 않도록 방문처리 작업을 해줘야 합니다.
• 모든 칸을 다 탐색하고 인접한 집 묶음에 발전기를 하나씩 놓아주면, 최소한의 발전기로 모든 집에 전력을 공급할 수 있습니다.
• BFS를 사용해 연결된 집들을 조사할 것입니다.

 

[ 집을 탐색할 때 사용할 알고리즘: BFS(Breadth-First Search, 너비 우선 탐색) ]

: 시작 정점으로부터 가가운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

위키피디아: BFS 알고리즘

특징
1) 재귀적으로 동작하지 않는다.
2) 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
3) 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐(Queue)를 사용한다.
-> FIFO(선입선출)을 원칙으로 탐색합니다.

 

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
} //출처: 백준 - 알고리즘 수업 - 너비 우선 탐색 1 (https://www.acmicpc.net/problem/24444)

---

풀이 과정

1. 0과 1로 이루어진 마을을 행렬 순으로 방문하면서 1(방문하지 않은 집)을 만나면 ->

    인접한 집 묶음에 놓을 발전기를 +1 해주고, 현재 집과 상하좌우로 닿아있는 모든 집을 BFS 함수를 사용해 탐색합니다.

int answer=0;//발전기 개수
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if(house[i][j]==1){ //집이 있고 방문한 적이 없는 집이면
            bfs(i,j,house,n);//dfs 탐색, 상하좌우로 연결된 집이 없을 때까지
            answer++;//발전기 추가
        }
    }
}

 

2. 현재 집에서 인접한 모든 집을 탐색할 BFS 함수를 만들어 줍니다.

따로 visited배열을 만들어 사용하는 것보다 입력값으로 받아온 int [][] 배열을 활용해 방문한 집은 2로 처리해 줍니다.

(-> 메모리 절약)

DFS로 하지 않는 이유 
마을의 범위가 1000*1000에 방향을 상하좌우 4방향씩 탐색하기 때문에 
재귀함수를 사용해 dfs를 구현하게 된다면 런타임 에러가 발생하였습니다.
런타임 에러 발생 이유는 [BFS로는 되는데 DFS로는 안되는 이유]에 대해 자세히 적어 놓았습니다.
이 문제에 조건을 잘 설정하면 DFS로도 풀 수 있다고 하지만, 또 다른 조건들을 고려하지 않기 위해 BFS를 사용했습니다.

 

static void bfs(int x, int y, int[][] house, int n){
    int[] dx={1,-1,0,0};//방향
    int[] dy={0,0,1,-1};

    Queue<int[]> q = new LinkedList<>();// 자료구조 Queue
    q.add(new int[]{x,y});//현재 위치 추가

    while(!q.isEmpty()){
        int[] now = q.poll();//방문한 집 위치

        house[now[0]][now[1]]=2;//방문처리

        for(int i=0;i<4;i++){//상하좌우
            int nx=now[0]+dx[i];//now에 인접한 다음 위치
            int ny=now[1]+dy[i];

            //(nx,ny)가 마을 범위를 벗어나지 않고, 방문한 적이 없는 집이면
            if(nx>=0 && nx<n && ny>=0 && ny<n && house[nx][ny]==1){
                house[nx][ny]=2;//방문처리 -> bfs는 여기서 방문처리 해야 중복 방문 안함.
                q.add(new int[]{nx,ny});//다음 위치 queue에 추가.
            }
        }
    }
}

 

3. 마을에 있는 모든 집들을 다 조사한 후, 발전기의 개수를 반환합니다.

---



전체 코드

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] s;
		
		int[][] house = new int[n][n];//입력받은 마을
		for(int i=0;i<n;i++){
			s = br.readLine().split(" ");
			for(int j=0;j<n;j++){
				house[i][j]=Integer.parseInt(s[j]);
			}
		}
		
		int answer=0;//발전기 개수
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(house[i][j]==1){ //집이 있고 방문한 적이 없는 집이면
					bfs(i,j,house,n);//dfs 탐색, 상하좌우로 연결된 집이 없을 때까지
					answer++;//발전기 추가
				}
			}
		}
		
		System.out.println(answer);//발전기 개수 출력
	}
	// (x,y)와 인접한 모든 집 탐색
	static void bfs(int x, int y, int[][] house, int n){
		int[] dx={1,-1,0,0};//방향
		int[] dy={0,0,1,-1};
		
		Queue<int[]> q = new LinkedList<>(); //큐 Queue
		q.add(new int[]{x,y});//현재 위치 추가
		
		while(!q.isEmpty()){
			int[] now = q.poll();//방문한 집 위치
			
			house[now[0]][now[1]]=2;//방문처리
			
			for(int i=0;i<4;i++){//상하좌우
				int nx=now[0]+dx[i];//now에 인접한 다음 위치
				int ny=now[1]+dy[i];
				
				//(nx,ny)가 마을 범위를 벗어나지 않고, 방문한 적이 없는 집이면
				if(nx>=0 && nx<n && ny>=0 && ny<n && house[nx][ny]==1){
					house[nx][ny]=2;//방문처리
					q.add(new int[]{nx,ny});//다음 위치를 queue에 추가.
				}
			}
		}
	}
}