🌞Algorithm/🔥Baekjoon

[Baekjoon] 15240_Paint bucket

뿌야._. 2024. 9. 23. 22:41
문제(출처: 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