[자바] 백준 8061 - Bitmap (java)

목차

문제 : boj8061

 

 

필요 알고리즘

• 너비 우선 탐색 (BFS)
  
  • BFS로 최단 거리를 얻어서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  문제에서 제시된 거리가 '|i1-i2|+|j1-j2|' 인 점에서 상하좌우로 한칸 움직인 것을 거리 1로 보는 '맨해튼 거리' 방식임을 알 수 있다. 이 문제에서 원하는건 결국 '1'인 위치들에서 출발해서 '0'인 위치들의 최단거리를 재는 것이다. 따라서 기본적인 BFS를 적용하면 풀 수 있다. BFS를 모른다면 '이 글'을 참고해보자.

 

  큐에 '1'인 곳들의 위치를 전부 등록해두고 거길 거리 0으로 잡는다. 그리고 BFS를 진행하면서 거리를 +1씩 늘려나가며 최단거리를 찾아주면 된다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, -1, 1, 0};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[][] dist = new int[r][c];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Queue<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                if (row.charAt(j) == '1') {
                    dist[i][j] = 0;
                    q.add(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            int curDist = dist[cr][cc];

            for (int d = 0; d < 4; d++) {
                int nr = cr+DR[d];
                int nc = cc+DC[d];

                if (nr<0 || nr>=r || nc<0 || nc>=c || dist[nr][nc] <= curDist+1) continue;
                dist[nr][nc] = curDist + 1;
                q.add(new int[]{nr, nc});
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                sb.append(dist[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}