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

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

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

2. 마을에 집에는 유형이 존재하며, 각 유형은 숫자로 구분합니다.

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

4. 단지는 상하좌우 인접한 같은 유형의 집 개수가 K보다 큰 집의 그룹입니다.

5. 단지가 가장 많은 집의 유형을 결과로 출력합니다.

6. 단지의 개수가 같으면 집의 유형 숫자가 더 큰 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 각 집에서 BFS탐색을 통해 각 유형 단지의 개수를 구합니다.

 

3. 단지의 개수가 가장 많은 유형의 숫자를 결과로 출력합니다.

 

 

구현

 

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

 

 

K = 2일 때

 

1(발전기)	3(발전기)	2(발전기)
3(→ , 전력 On)	3(↑, 전력 On)	2(↑, 전력 On)
2(→ , 전력 On)	2(→ , 전력 On)	2(↑, 전력 On)

 

단지를 구성하기 위해서 BFS을 사용하였습니다.

 

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

 

BFS탐색이 끝났을 때,

 

유형 1 : 단지 개수 0개

 

유형 2 : 단지 개수 1개

 

유형 3 : 단지 개수 1개

 

유형 2와 유형 3의 단지 개수가 같아서 유형의 숫자가 더 큰 값을 결과로 출력하기 때문에 결과는 3입니다.

 

예제입력 1.

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

 

N : 3

 

K : 2

 

1	1	3
2	2	3
3	3	2

 

2. 각 집에서 BFS탐색을 통해 각 유형 단지의 개수를 구합니다.

 

단지에 속하지 않는 집(0, 0) 탐색

 

BFS탐색 진행!(유형 1)

 

 

1	1	3
2	2	3
3	3	2

 

집의 개수(2) ≥ K(2)가 성립하기 때문에 단지로써 역활을 할 수 있습니다.

 

유형	1	2	3
단지 개수	1	0	0

 

단지에 속하지 않는 집(0, 2) 탐색

 

BFS탐색 진행!(유형 3)

 

 

1	1	3
2	2	3
3	3	2

 

집의 개수(2) ≥ K(2)가 성립하기 때문에 단지로써 역활을 할 수 있습니다.

 

유형	1	2	3
단지 개수	1	0	1

 

단지에 속하지 않는 집(1, 0) 탐색

 

BFS탐색 진행!(유형 2)

 

 

1	1	3
2	2	3
3	3	2

 

집의 개수(2) ≥ K(2)가 성립하기 때문에 단지로써 역활을 할 수 있습니다.

 

유형	1	2	3
단지 개수	1	1	1

 

단지에 속하지 않는 집(2, 0) 탐색

 

BFS탐색 진행!(유형 3)

 

 

1	1	3
2	2	3
3	3	2

 

집의 개수(2) ≥ K(2)가 성립하기 때문에 단지로써 역활을 할 수 있습니다.

 

유형	1	2	3
단지 개수	1	1	2

 

단지에 속하지 않는 집(2, 2) 탐색

 

BFS탐색 진행!(유형 2)

 

 

1	1	3
2	2	3
3	3	2

집의 개수(1) ≥ K(2)가 성립하기 때문에 단지로써 역활을 할 수 있습니다.

 

유형	1	2	3
단지 개수	1	1	2

 

더 이상 단지에 속하지 않는 집은 없습니다!!!

 

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

 

유형	1	2	3
단지 개수	1	1	2

 

K이상의 집을 가진 단지 개수가 가장 많은 유형은 3번입니다.

 

3을 결과로 출력합니다.

 

• 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 {
    //상하좌우 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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] town = new int[M][M];
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++){
                town[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //마을 단지 확인 여부 배열
        boolean[][] visited = new boolean[M][M];
        //단지 개수 배열
        int[] complexCnt = new int[31];
        //BFS 탐색 진행
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                //이미 단지에 속하는지 탐색한 집일 때
                if(visited[i][j]){
                    continue;
                }
                //BFS탐색으로 단지 개수 더하기
                complexCnt[town[i][j]] += search(i, j, town, visited, M, K);

            }
        }
        //단지 개수 최대값 변수
        int max = 0;
        //단지 개수 최대값 관련 유형 변수
        int result = 0;
        //단지 개수 최대값 유형 구하기
        for(int i=1;i<31;i++){
            if(complexCnt[i] == 0){
                continue;
            }
            if(complexCnt[i] >= max){
                max = complexCnt[i];
                result = i;
            }
        }
        //단지 최대값 유형 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 이용하여 상하좌우 같은 집 탐색하여 단지 구분하는 함수
    static int search(int r, int c, int[][] town, boolean[][] visited, int M, int K){
        //BFS에 사용할 Queue
        Queue<Pos> queue = new ArrayDeque<>();
        //초기 집 저장
        queue.offer(new Pos(r, c));
        //초기 집 단지 탐색 확인
        visited[r][c] = true;
        int cnt = 1;
        //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, M) && !visited[tempR][tempC] && town[tempR][tempC] == town[r][c]){
                    //인접한 집 Queue 저장
                    queue.offer(new Pos(tempR, tempC));
                    visited[tempR][tempC] = true;
                    cnt++;		//집 개수 증가
                }
            }
        }

        //집의 개수가 K보다 작으면 올바르 단지로 인식 X
        if(cnt < K){
            return 0;
        }else{		//집의 개수가 K이상일 때 올바른 단지 O
            return 1;
        }

    }
    //인접한 집이 마을 내에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c, int M){
        //마을 내 존재하는 집일 때
        if(r >= 0 && r < M && c >= 0 && c < M){
            return true;
        }
        return false;
    }
}

 

---

느낀 점

 

이전에 구름톤에서 풀었던 문제  발전기 문제와 비슷하지만 살짝 다른 느낌을 받았습니다.

 

기존에 풀었던 발전기 문제를 조금 응용하였더니 쉽게 풀리게 되었습니다.

 

문제를 풀고 확실히 이해하고 있어야 비슷한 문제가 나와도 풀 수 있다는 것을 느끼게 되었습니다.

 

그로 인해 하나의 문제를 풀 때도 정확하게 이해하고 넘어가는 것에 중요성을 깨닫게 되었습니다.