[Baekjoon] 8061_Bitmap

문제(출처: https://www.acmicpc.net/problem/8061)

---

< Bitmap >

 

문제 풀이 

 

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 _8061_ { // Bitmap
	static int result[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	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 n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		result = new int[n][m];

		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) - '0' == 0) {
					result[i][j] = Integer.MAX_VALUE;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (result[i][j] == 0) {
					bfs(i, j);
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				bw.write(result[i][j] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
	}

	private static void bfs(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < result.length && y >= 0 && y < result[0].length && result[x][y] != 0
						&& result[x][y] > result[temp[0]][temp[1]] + 1) {
					result[x][y] = result[temp[0]][temp[1]] + 1;
					queue.add(new int[] { x, y });
				}
			}
		}
	}
}

 

변수)
n, m : 배열 크기
result : 배열
dx, dy : 상, 하, 좌, 우

 

배열 크기를 입력받아 배열 크기만큼 정보를 입력받으며 0인 경우 정수 최댓값으로 저장한다. 배열을 전체 탐색하면서 값이 0이라면 bfs 함수를 호출한다. 최종 result 배열을 출력한다.

 

bfs(int i, int j)

Queue에 시작 위치를 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 0이 아니고 최솟값으로 업데이트 가능하다면 최솟값 업데이트 및 queue에 추가

---

---