백준 27211 - 도넛 행성

문제

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

리뷰

BFS를 이용하여 풀이할 수 있는 간단한 문제였다.

기존의 상하좌우 방향으로 BFS 탐색을 진행하며 최단 경로 비용을 구하는
문제들의 조건에서 인덱스 범위를 넘어서는 경우만 문제 조건에 따라 특수적으로
처리해 이동할 수 있게 해주면 되는 문제였다.

로직의 시간복잡도는 BFS에서 $O(V^2)$의 형태이고 이는 문제에서 $O(NM)$의
형태를 띠므로 최악의 경우인 $NM=10^6$의 경우에도 제한 조건 1초를 무난히
통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        M = parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        List<Point> empty = new ArrayList<>();
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < M; c++) {
                map[r][c] = parseInt(st.nextToken());
                if (map[r][c] == 0) empty.add(new Point(r, c));
            }
        }

        int area = 0;
        for (Point p : empty) {
            if (!visited[p.r][p.c]) {
                bfs(p);
                area++;
            }
        }

        System.out.println(area);
        br.close();
    }

    static void bfs(Point start) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        Queue<Point> queue = new ArrayDeque<>();
        visited[start.r][start.c] = true;
        queue.offer(start);

        int nr, nc;
        while (!queue.isEmpty()) {
            Point cur = queue.poll();

            for (int i = 0; i < dr.length; i++) {
                nr = cur.r + dr[i];
                nc = cur.c + dc[i];

                if (nr < 0) nr = N - 1;
                if (nc < 0) nc = M - 1;
                if (nr >= N) nr = 0;
                if (nc >= M) nc = 0;

                if (map[nr][nc] == 1) continue;

                if (visited[nr][nc]) continue;

                visited[nr][nc] = true;
                queue.offer(new Point(nr, nc));
            }
        }
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

결과