[백준] 8061번 - Bitmap

문제 >

here is given a rectangular bitmap of size n x m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in i-th line and j-th column is called the pixel (i,j). The distance between two pixels p1=(i1,j1) and p2=(i2,j2) is defined as:

d(p1,p2)=|i1-i2|+|j1-j2|.

Write a program which:

• reads the description of the bitmap from standard input,
• for each pixel, computes the distance to the nearest white pixel,
• writes the results to the standard output.
  
  

입력 >

First line of the standard input there is a pair of integer numbers n, m separated by a single space, 1 ≤ n ≤ 182, 1 ≤ m ≤ 182. In each of the following n lines of the input exactly one zero-one word of length m, the description of one line of the bitmap, is written. On the j-th position in the line (i+1), 1 ≤ i ≤ n, 1 ≤ j ≤ m, is 1 if, and only if the pixel (i,j) is white.

 

출력 >

In the i-th line of the standard output, 1 ≤ i ≤ n, there should be written m integers f(i,1),…,f(i,m) separated by single spaces, where f(i,j) is the distance from the pixel (i,j) to the nearest white pixel.

 

해결방법 > 

BFS. 원소값이 1인 정점으로부터 원소값이 0인 정점까지 최단거리를 저장한다. 

 

1) 원소값이 1인 정점을 큐에 저장한다.

 

2) 인접한 정점(원소값이 0이면서 방문하지 않는 정점)을 방문하면서 1부터 정점까지의 최단거리를 저장한다.

 

[JAVA]

package baekjoon;

import java.util.*;
import java.io.*;

public class BOJ_8061 {
	public static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(tk.nextToken());
		int m = Integer.parseInt(tk.nextToken());
		int[][] map = new int[n][m];
		int[][] visit = new int[n][m];
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, 1, 0, -1};
		
		Queue<Node> q = new LinkedList<>();
		for(int i = 0; i < n; i++) {
			String s = br.readLine();
			for(int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j) - '0';
				map[i][j] = map[i][j] == 1 ? 0 : 1;
				if(map[i][j] == 0) {
					visit[i][j] = 1;
					q.add(new Node(i, j));
				}
			}
		}
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				
				if(nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 1 && visit[nx][ny] == 0) {
					visit[nx][ny] = visit[node.x][node.y] + 1;
					q.add(new Node(nx, ny));
				}
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				System.out.print(visit[i][j] - 1 + " ");
			}
			System.out.println();
		}
	}
}