[ BOJ 백준 8061번 - Bitmap ] 해설 및 코드

https://www.acmicpc.net/problem/8061

 

목적

임의의 (i, j)에서 1이 있는 좌표(white pixel)와의 최단 거리를 구하자.

 

접근법

1. white pixel들의 좌표를 모두 queue에 담아 bfs 알고리즘을 이용하여 거리를 갱신해준다.

 

#include<iostream>
#include<queue>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
struct info { int i, j, k; };
char p[183][183];
int n, m, ans[183][183], di[] = { 1,-1,0,0 }, dj[] = { 0,0,1,-1 };
 
void spread(queue<info>& q) {
    while (!q.empty()) {
        int i = q.front().i, j = q.front().j, k = q.front().k;
        q.pop();
        f(d, 0, 4) {
            int ni = i + di[d], nj = j + dj[d], nk = k + 1;
            if (ni < 0 || ni >= n || nj < 0 || nj >= m || nk >= ans[ni][nj]) continue;
            ans[ni][nj] = nk;
            q.push({ ni,nj,nk });
        }
    }
}
 
int main() {
    cin >> n >> m;
    f(i, 0, n)cin >> p[i];
    
    queue<info> q;
    f(i, 0, n)f(j, 0, m) {
        if (p[i][j] == '1') {
            ans[i][j] = 0;
            q.push({ i,j,0 });
        }
        else ans[i][j] = 400;
    }
 
    spread(q);
 
    f(i, 0, n) {
        f(j, 0, m)cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.