문제(출처: https://www.acmicpc.net/problem/15240)
< Paint bucket >
문제 풀이
bfs를 사용하여 문제를 해결한다.
my solution (Java)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class _15240_ { // Paint bucket
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int arr[][] = new int[R][C];
for (int i = 0; i < R; i++) {
String str = bf.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = str.charAt(j) - '0';
}
}
st = new StringTokenizer(bf.readLine());
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
if (arr[X][Y] != K) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { X, Y });
int c = arr[X][Y];
arr[X][Y] = K;
while (!queue.isEmpty()) {
int temp[] = queue.poll();
for (int i = 0; i < 4; i++) {
int a = temp[0] + dx[i];
int b = temp[1] + dy[i];
if (a >= 0 && a < R && b >= 0 && b < C && arr[a][b] == c) {
arr[a][b] = K;
queue.add(new int[] { a, b });
}
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
bw.write(arr[i][j] + "");
}
bw.write("\n");
}
bw.flush();
}
}
변수)
R, C : 배열 크기
arr : 배열
X, Y, K : 바꿀 위치, 색칠해야 하는 숫자
dx, dy : 상하좌우
c : 원래 숫자
배열 크기 R, C를 입력받는다. 배열 값을 입력받아 arr에 저장한다. 바꿀 위치와 색을 입력받는다. 바꿀 위치를 기준으로 bfs를 사용하여 상하좌우 탐색을 통해 원래 같은 값을 찾아 K로 바꾼다.
'🌞Algorithm > 🔥Baekjoon' 카테고리의 다른 글
[Baekjoon] 11448_Ga (1) | 2024.09.25 |
---|---|
[Baekjoon] 6189_Munching (0) | 2024.09.24 |
[Baekjoon] 4993_Red and Black (1) | 2024.09.13 |
[Baekjoon] 6031_Feeding Time (0) | 2024.09.12 |
[Baekjoon] 5958_Space Exploration (0) | 2024.09.11 |