[Baekjoon 15240] Paint bucket - JAVA

문제 링크

성능 요약

메모리: 74560 KB, 시간: 712 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill” operation.

When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color than the target pixel and are connected to it. Two pixels are connected if they share a side or if they are connected through a path of connected pixels.

Let’s see an example: In the following image, if we select the “fill” operation in an image editor program and click on the center of the image (orange pixel). The whole region will be painted orange. Notice that the pixels are not connected diagonally so two corners of the image remain white.

)

Your task is: Given a matrix of digits representing the pixels, simulated what would be the result of a “fill” operation on given pixels. Thus, the colors will be represented with a number from 0 to 9.

Let’s see another example, now using digits instead of pixels. We have the following image:

0000000
0111000
0111010
0000000

If we “fill” at position Y = 0, X = 0 with color 3, all the 0s get painted of color 3. Because all of them are recursively connected.

The result will be:

3333333
3111333
3111313
3333333

입력

The first line will contain two integers R and C representing the number of rows and columns of the image.

The next R lines will contain C digits each representing the initial colors of the pixels.

The last line will contain 3 integers Y, X and K representing the row and column where we want to apply the “fill” operation and the color to use.

The images will be smaller than 1000 x 1000 pixels.

The colors are limited to a single digit from 0 to 9.

출력

Print the resulting image after applying the operation in the same format as the input.

문제 풀이

해당 문제는 입력으로 그림과 시작 좌표, 바꿔진 숫자가 주어진다.

시작 위치에서 같은 숫자까지의 범위를 입력되어진 숫자로 변경 시키는 문제다.

그림에서 숫자를 변경하기 위한 조건은 아래와 같다.

1. x, y값이 음수가 아닐것
2. x, y값이 그림의 크기를 벗어나지 않을것
3. 해당 값이 이미 지정한 숫자로 변경하지 않았을 경우
4. 해당 값이 시작 위치의 숫자와 같을 경우

위의 경우가 모두 해당할 경우 지정된 숫자로 변경해주면 된다.

이를 이용하여 dfs 코드를 짜보았다.

static int R, C, X, Y, K, num;    // 입력 받을 값들과 num은 바꿔지는 숫자를 저장하는 변수
static int [][] matrix;    // 그림을 입력받을 배열
static int [] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};    // 행 열이 이동하면서 사용될 배열

static void dfs() {
    boolean [][] visited = new boolean[R][C];    // 바꿀 값인지 아닌지 저장할 변수
    Queue<int []> queue = new LinkedList<>();
    queue.add(new int[] {X, Y});    // 큐에 시작 위치 x, y값을 넣는다
    visited[X][Y] = true;    // 시작 위치는 바꿀 숫자와 동일하다.
    matrix[X][Y] = K;    // 입력한 숫자로 바꿔준다.

    while(!queue.isEmpty()) {    // 큐가 비어있지 않을때
        int x = queue.peek()[0];    // peek를 사용해서 0번째 큐에 들어온 값을 저장 
        int y = queue.peek()[1];    // peek를 사용해서 1번째 큐에 들어온 값을 저장
        queue.poll();    // 큐 값을 빼준다.

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];    // x값 이동
            int ny = y + dy[i];    // y값 이동
            if (nx < 0 || ny < 0 || nx >= R || ny >= C || visited[nx][ny]) continue;
            // x, y값이 음수이거나, x, y값이 그림 크기보다 크거나 방문했던곳이라면 continue를 실행한다.
            visited[nx][ny] = true;    // 이동한곳에 배열에 true를 집어넣는다.
            if (num == matrix[nx][ny]) {    // 바꿔야 할 숫자와 그림에 숫자가 같다면
                matrix[nx][ny] = K;    // 입력한 숫자로 바꿔준다.
                queue.add(new int[] {nx, ny});    // 큐에 nx와 ny값을 넣어준다.
                }
            }
        }
    }

위 코드를 이용하여 전체적인 코드를 짜면 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int R, C, X, Y, K, num;    // 입력 받을 값들과 num은 바꿔지는 숫자를 저장하는 변수
    static int [][] matrix;    // 그림을 입력받을 배열
    static int [] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};    // 행 열이 이동하면서 사용될 배열

    static void dfs() {    // 깊이 우선 탐색
        boolean [][] visited = new boolean[R][C];    // 바꿀 값인지 아닌지 저장할 변수
        Queue<int []> queue = new LinkedList<>();    // 큐 선언
        queue.add(new int[] {X, Y});    // 큐에 시작 위치 x, y값을 넣는다
        visited[X][Y] = true;    // 시작 위치는 바꿀 숫자와 동일하다.
        matrix[X][Y] = K;    // 입력한 숫자로 바꿔준다.

        while(!queue.isEmpty()) {    // 큐가 비어있지 않을때
            int x = queue.peek()[0];    // peek를 사용해서 0번째 큐에 들어온 값을 저장 
            int y = queue.peek()[1];    // peek를 사용해서 1번째 큐에 들어온 값을 저장
            queue.poll();    // 큐 값을 빼준다.

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];    // x값 이동
                int ny = y + dy[i];    // y값 이동
                if (nx < 0 || ny < 0 || nx >= R || ny >= C || visited[nx][ny]) continue;
                // x, y값이 음수이거나, x, y값이 그림 크기보다 크거나 방문했던곳이라면 continue를 실행한다.
                visited[nx][ny] = true;    // 이동한곳에 배열에 true를 집어넣는다.
                if (num == matrix[nx][ny]) {    // 바꿔야 할 숫자와 그림에 숫자가 같다면
                    matrix[nx][ny] = K;    // 입력한 숫자로 바꿔준다.
                    queue.add(new int[] {nx, ny});    // 큐에 nx와 ny값을 넣어준다.
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());    // 행을 나타내는 정수
        C = Integer.parseInt(st.nextToken());    // 열을 나타내는 정수
        matrix = new int[R][C];    // 그림을 입력할 배열 크기 지정

        for (int x = 0; x < R; x++) {
            String line = br.readLine();    // 행 입력
            for (int y = 0; y < C; y++) {
                matrix[x][y] = line.charAt(y) - '0';    // charAt로 입력한 행을 배열에 넣음
            }
        }

        st = new StringTokenizer(br.readLine());

        X = Integer.parseInt(st.nextToken());    // 시작하는 위치의 x값
        Y = Integer.parseInt(st.nextToken());    // 시작하는 위치의 y값
        K = Integer.parseInt(st.nextToken());    // 바꿔진 숫자

        num = matrix[X][Y];    // 바꿔야 하는 숫자가 몇인지 num에 저장
        dfs();    // dfs 사용

        for (int x = 0; x < R; x++) { 
            for (int y = 0; y < C; y++) {
                sb.append(matrix[x][y]);    // sb에 값 추가
            }
            sb.append("\n");    // sb에 값 추가
        }
        System.out.println(sb);    // sb 출력
    }
}