27211_도넛 행성

사용 알고리즘: bfs

사용 언어: java

 

 

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_bj_27211_도넛행성 {
    static int n,m;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == 0 && !visited[i][j]) {
                    ans++;
                    visited[i][j] = true;
                    bfs(i, j);
                }
            }
        }

        System.out.println(ans);
    }

    private static void bfs(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(x, y));

        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = p.x + dx[d];
                int ny = p.y + dy[d];

                //범위 벗어나면 돌리기
                if(nx < 0) {
                    nx = n + nx;
                }
                if(ny < 0) {
                    ny = m + ny;
                }
                if(nx >= n) {
                    nx = nx - n;
                }
                if(ny >= m) {
                    ny = ny - m;
                }

                //방문 확인 후 안 했으면 큐에 넣기
                if(map[nx][ny] != 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny));
                }
            }
        }
    }
}

 

 

주의점:

범위를 벗어나면 그대로 continue가 아니라,

이어 버린다