[백준][Java] 15240 - Paint bucket

목차

 

문제 정보

https://www.acmicpc.net/problem/15240

15240번: Paint bucket

난이도 : S1

유형 : BFS, DFS

 

---

문제 풀이

상하좌우로 같은 문자를 탐색하면서 치환해 주면 된다.

여기서 주의할점은 기존 문자와 입력으로 주어진 문자가 같다면 로직을 진행하지 않고 출력만 해주면 된다.

또는 탐색 시 방문체크를 해줘도 된다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ_15240
 * author - devteo77
 */

public class Main {

    final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int R;
    int C;
    int Y;
    int X;
    char K;
    char[][] board;

    public void execBFS() {

        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{Y, X});

        char originCh = board[Y][X];

        if (originCh == K) {
            return;
        }

        board[Y][X] = K;
        while (!que.isEmpty()) {
            int[] cur = que.poll();

            for (int i = 0; i < dir.length; i++) {
                int nX = cur[0] + dir[i][0];
                int nY = cur[1] + dir[i][1];

                if (nX < 0 || nX >= R || nY < 0 || nY >= C) {
                    continue;
                }

                if (board[nX][nY] != originCh) {
                    continue;
                }

                que.add(new int[]{nX, nY});
                board[nX][nY] = K;
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        board = new char[R][C];

        for (int i = 0; i < R; i++) {
            board[i] = br.readLine().toCharArray();
        }

        st = new StringTokenizer(br.readLine());
        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        K = st.nextToken().charAt(0);

        execBFS();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sb.append(board[i][j]);
            }
            sb.append('\n');
        }

        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}