[구름톤 챌린지, Java] 20일차, 연결 요소 제거하기(BFS, 구현)

문제 링크

구름LEVEL

---

 

접근 방법

이 문제에 핵심

1. N × N 배열에는 알파벳 또는 '.' 가 적혀있습니다.

2. 상하좌우 인접한 칸에 같은 알파벳이 존재하면 두 칸은 연결되어 있다고 판단하며, 이 집합을 연결 요소라고 합니다.

3. Q번 아래와 같은 과정을 진행합니다.

4. Q번 과정을 실행한 이후에 N × N 배열의 값들을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. Q번 동안 문제에서 설명한 과정을 BFS을 통해서 진행합니다.

 

3. Q번 진행한 이후 배열의 값들을 결과로 출력합니다.

 

 

구현

 

Q번 동안 문제에 설명한 내용의 과정을 진행합니다.

 

N : 3

 

K : 2

 

 

.	.	.
A	.	.
.	.	.

 

(2, 2, A)가 진행되는 과정을 살펴보겠습니다.

.	.	.
A	A	.
.	.	.

.	.	.
A	A	.
.	.	.

(2, 2)를 기준으로 알파벳 대문자 'A'인 연결고리를 BFS탐색하면

{ (2, 1), (2, 2) }의 2개의 연결고리가 만들어집니다.

 

연결고리의 개수(2) ≥ K(2)

 

성립하므로 해당 칸에 적힌 요소들을 제거합니다!!

 

.	.	.
.	.	.
.	.	.

 

위 과정을 Q번 반복하면 끝입니다.

 

예제입력 1.

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

 

N : 5

K : 5

Q : 6

 

A	B	.	.	C
B	B	A	Z	Z
.	.	.	.	A
B	B	B	.	B
C	C	B	A	B

 

2. Q번 동안 문제에서 설명한 과정을 BFS을 통해서 진행합니다.

 

(3, 4, A) 진행!

 

A	B	.	.	C
B	B	A	Z	Z
.	.	.	A	A
B	B	B	.	B
C	C	B	A	B

 

BFS 탐색 진행

 

A	B	.	.	C
B	B	A	Z	Z
.	.	.	A	A
B	B	B	.	B
C	C	B	A	B

 

{ (3, 4), (3, 5) }의 2개의 연결고리

 

연결고리의 개수(2) ≥ K(5)

 

성립하지 않으므로 제거하지 않습니다.

 

(3, 1, A) 진행!

 

A	B	.	.	C
B	B	A	Z	Z
A	.	.	A	A
B	B	B	.	B
C	C	B	A	B

 

BFS 탐색 진행

 

A	B	.	.	C
B	B	A	Z	Z
A	.	.	A	A
B	B	B	.	B
C	C	B	A	B

 

{ (3, 1) } 의 1개의 연결고리

 

연결고리의 개수(1) ≥ K(5)

 

성립하지 않으므로 제거하지 않습니다.

 

(3, 3, A) 진행!

 

A	B	.	.	C
B	B	A	Z	Z
A	.	A	A	A
B	B	B	.	B
C	C	B	A	B

 

BFS 탐색 진행

 

A	B	.	.	C
B	B	A	Z	Z
A	.	A	A	A
B	B	B	.	B
C	C	B	A	B

 

{ (3, 3), (3, 4), (3, 5) } 의 3개의 연결고리

 

연결고리의 개수(3) ≥ K(5)

 

성립하지 않으므로 제거하지 않습니다.

 

(3, 2, B) 진행!

 

A	B	.	.	C
B	B	A	Z	Z
A	B	A	A	A
B	B	B	.	B
C	C	B	A	B

 

BFS 탐색 진행

 

A	B	.	.	C
B	B	A	Z	Z
A	B	A	A	A
B	B	B	.	B
C	C	B	A	B

 

{ (1, 2), (2, 1), (2, 2), (3, 2), (4, 1), (4, 2), (4, 3), (5, 3) } 의 8개의 연결고리

 

연결고리의 개수(8) ≥ K(5)

 

성립하므로 해당 칸에 적힌 요소들을 제거합니다!!

 

A	.	.	.	C
.	.	A	Z	Z
A	.	A	A	A
.	.	.	.	B
C	C	.	A	B

 

(3, 2, A) 진행!

 

A	.	.	.	C
.	.	A	Z	Z
A	A	A	A	A
.	.	.	.	B
C	C	.	A	B

BFS 탐색 진행

A	.	.	.	C
.	.	A	Z	Z
A	A	A	A	A
.	.	.	.	B
C	C	.	A	B

{ (2, 3), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5) } 의 6개의 연결고리

 

연결고리의 개수(6) ≥ K(5)

 

성립하므로 해당 칸에 적힌 요소들을 제거합니다!!

 

A	.	.	.	C
.	.	.	Z	Z
.	.	.	.	.
.	.	.	.	B
C	C	.	A	B

 

(1, 2, D) 진행!

 

A	D	.	.	C
.	.	.	Z	Z
.	.	.	.	.
.	.	.	.	B
C	C	.	A	B

BFS 탐색 진행

A	D	.	.	C
.	.	.	Z	Z
.	.	.	.	.
.	.	.	.	B
C	C	.	A	B

{ (2, 2) } 의 1개의 연결고리

연결고리의 개수(1) ≥ K(5)

 

성립하지 않으므로 제거하지 않습니다.

 

3. Q번 진행한 이후 배열의 값들을 결과로 출력합니다.

 

Q번 진행한 결과

 

A	D	.	.	C
.	.	.	Z	Z
.	.	.	.	.
.	.	.	.	B
C	C	.	A	B

 

 을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• Q번동안 문제에서 설명한 과정을 search함수를 통해 진행합니다.
• Q번 동작 이후 배열의 정보를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 상하좌우 인접한 연결고리를 생성합니다.
• search함수는 연결요소의 개수가 K 이상이면 '.'으로 대체합니다.
• inSpace함수는 이동하려는 칸이 배열에 존재하는지 확인합니다.

 

결과코드

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

class Main {
    //배열 위치 정보 관련 클래스
    static class Pos{
        /*
        y : y 위치값
        x : x 위치값
        */
        int y, x;
        public Pos(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
    //상하좌우 y, x 변경 값 배열
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    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 N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        char[][] arr = new char[N][N];
        //배열 정보 저장
        for(int i=0;i<N;i++){
            String str = br.readLine();
            Arrays.fill(arr[i],'.');
            for(int j=0;j<N;j++){
                arr[i][j] = str.charAt(j);
            }
        }
        //Q번의 과정 진행
        for(int i=0;i<Q;i++){
            st = new StringTokenizer(br.readLine()," ");
            //Q의 대한 입력값 저장
            int y = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken())-1;
            char d = st.nextToken().charAt(0);
            arr[y][x] = d;
            //BFS을 통한 연결요소 구하기
            search(arr, y, x, d, K, N);
        }
        StringBuilder sb = new StringBuilder();
        //Q번 과정을 끝낸 뒤 배열 정보 StringBuilder 저장
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }
        //StringBuilder 저장된 결과 BufferedWriter 저장
        bw.write(sb.toString());		//결과 출력
        bw.flush();
        bw.close();
        br.close();
    }
    //BFS을 통해서 상하좌우 연결고리 만드는 함수
    static void search(char[][] arr, int y, int x, int d, int k, int N){
        //BFS에 사용할 Queue
        Queue<Pos> queue = new ArrayDeque<>();
        //연결 고리에 속한 연결 요소 정보 저장 List
        List<Pos> list = new ArrayList<>();
        //현재 위치 값 연결고리에 추가
        list.add(new Pos(y, x));
        boolean[][] visited = new boolean[N][N];
        //현재 위치 Queue 저장
        queue.offer(new Pos(y, x));
        //현재 위치 방문 확인
        visited[y][x] = true;
        //BFS을 통한 연결 고리 만들기 진행
        while(!queue.isEmpty()){
            Pos cur = queue.poll();
            //상하좌우 인접한 칸 탐색
            for(int i=0;i<4;i++){
                int tempY = cur.y + dy[i];
                int tempX = cur.x + dx[i];
                //배열에 존재하며, 방문하지 않았으며, 같은 알파벳일 때
                if(inSpace(tempY, tempX, N) && !visited[tempY][tempX] && arr[tempY][tempX] == d){
                    visited[tempY][tempX] = true;
                    //연결고리에 속한 연결 요소 List에 저장
                    list.add(new Pos(tempY,tempX));
                    queue.offer(new Pos(tempY,tempX));
                }
            }
        }
        //연결요소 개수 ≥ K가 성립할 때
        if(list.size() >= k){
            //연결고리에 속한 연결요소 모두 '.'으로 변환
            for(Pos cur : list){
                arr[cur.y][cur.x] = '.';
            }
        }
    }
    //이동하려는 칸이 배열에 존재하는지 확인하는 함수
    static boolean inSpace(int y, int x, int N){
        if(y >= 0 && x >= 0 && y < N && x < N){
            return true;
        }
        return false;
    }
}

 

---

느낀 점

 

길다면 길고, 짧다면 짧은 마지막 구름톤 문제 20일차가 종료되었습니다.

 

중간에 심하게 소화불량이 일어나서 문제를 풀 때에 힘들었던 경험이 있었지만, 성실하게 모든 문제를 풀게되어서 매우 뿌듯합니다.

 

이후, 오프라인 팀 첼린지에도 50명 추첨이지만 꼭 참여해서, 다른 사람들과 정보들을 공유해보고 싶습니다.

 

고생했다!! 내 자신!!