[구름톤 챌린지, Java] 12일차, 발전기(BFS)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. N길이의 정사각형 모양의 마을이 존재합니다.

2. 마을에는 0과 1이 존재하며 0은 빈 집, 1은 집이 존재한다는 뜻입니다.

3. 각 집에는 발전기를 설치할 수 있으며, 상하좌우 인접한 집이 전력을 받고 있으면 해당 집도 전력을 받을 수 있습니다.

4. 모든 집이 전력을 공급받을 수 있는 발전기 설치 최소 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 집에서 BFS탐색을 통해 그룹의 개수를 구합니다.

 

3. 그룹의 개수는 최소 발전기의 개수이므로 결과로 출력합니다.

 

 

구현

 

각 그룹에 속하지 않는 집을 기준으로 BFS탐색을 통해서 그룹을 조성합니다.

 

 

그룹을 조성하는 이유?

 

 

상하좌우로 인접한 집끼리 그룹을 만들면, 모두 전력을 공급받을 수 있기 때문입니다.

 

 

1(발전기)	0	1(발전기)
0	0	1(↑, 전력 On)
1(→ , 전력 On)	1(→ , 전력 On)	1(↑, 전력 On)

 

 위처럼 점화식으로 표현하면

 

그룹의 개수 = 최소 발전기의 개수 

 

 

그룹의 개수를 구하기 위해서 BFS을 사용하였습니다.

 

그룹에 속하지 않는 집을 기준으로 BFS을 진행하여 그룹의 형태로 만들어주었습니다. 

 

BFS탐색이 끝났을 때,

 

그룹의 개수가 결과값으로 출력합니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 3

 

0	1(🏠)	0
1(🏠)	0	1(🏠)
1(🏠)	1(🏠)	1(🏠)

 

2. 각 집에서 BFS탐색을 통해 그룹의 개수를 구합니다.

 

그룹에 속하지 않는 집(0, 2)

 

BFS탐색 진행!

 

0	1(🏠)	0
1(🏠)	0	1(🏠)
1(🏠)	1(🏠)	1(🏠)

 

그룹에 속하지 않는 집(1, 0) 

 

BFS탐색 진행!

 

 

0	1(🏠)	0
1(🏠)	0	1(🏠)
1(🏠)	1(🏠)	1(🏠)

 

더 이상 그룹에 존재하지 않는 집은 없습니다!!!

 

그룹의 개수 : 2개

 

3. 그룹의 개수는 최소 발전기의 개수이므로 결과로 출력합니다.

 

그룹의 개수 = 최소 발전기의 개수

 

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 그룹에 속하지 않는 집들 기준 search함수를 통해 그룹핑 진행합니다.
• 그룹핑이 끝난 뒤 그룹의 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 상하좌우 인접한 집들을 그룹핑합니다.
• inSpace함수는 이동하려는 칸이 마을에 존재하는지 확인하는 함수입니다.

 

결과코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    //집 그룹 확인 배열
    static boolean[][] visited;
    //상하좌우 y 변경값
    static int[] dr = {-1, 1, 0, 0};
    //상하좌우 x 변경값
    static int[] dc = {0, 0, -1, 1};
    //좌표 정보 관련 클래스
    static class Pos{
        //r : y좌표, c : x좌표
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //마을 정보 저장 배열 초기화
        int[][] arr = 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++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int result = 0;
        //그룹에 속하지 않는 집 BFS탐색 진행
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                //그룹에 속하거나 집이 아닌 공간일 때
                if(visited[i][j] || arr[i][j] == 0){
                    continue;
                }
                //그룹의 개수 증가
                result++;
                //BFS탐색을 통해 그룹핑 진행
                search(i, j, N, arr);
            }
        }
        //그룹의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 통해 인접 집 그룹핑 진행하는 함수
    static void search(int r, int c, int N, int[][] arr){
        //BFS에 사용할 Queue
        Queue<Pos> queue = new ArrayDeque<>();
        queue.add(new Pos(r, c));
        //시작 위치 그룹 확인
        visited[r][c] = true;
        //BFS탐색 진행
        while(!queue.isEmpty()){
            Pos cur = queue.poll();
            //상하좌우 인접 공간 탐색
            for(int i=0;i<4;i++){
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                //마을에 존재하며, 집이며, 그룹에 존재하지 않을 때
                if(inSpace(tempR,tempC, N) && arr[tempR][tempC] == 1 && !visited[tempR][tempC]){
                    //집 그룹 확정
                    visited[tempR][tempC] = true;
                    queue.add(new Pos(tempR, tempC));
                }
            }
        }
    }
    //이동하려는 칸이 마을에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c, int N){
        //마을에 존재할 때
        if(r >= 0 && r < N && c >= 0 && c < N){
            return true;
        }
        return false;
    }
}

 

---

느낀 점

 

문제를 보았을 때 인접한 집 사이에 연결되어야 한다는 내용이 핵심적이라는 것을 파악하였습니다.

 

구름톤을 진행하면서 문제를 파악하는 실력이 늘은 것 같아서 뿌듯합니다.