백준 27211 (도넛 행성) - java

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

 

문제

준겸이는 N,M칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다.

준겸이는 본인의 집이 있는 위치를 기준으로 삼아 (0,0)이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 (0,1)에 도달할 것이다. 마찬가지로 아래로 한 칸 걸어가면, 위치 (1,0)$(1,0)$에 도달할 것이다. 준겸이가 (0,0)에서 M칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다. 비슷하게 (0,0)에서 N칸 아래로 걸어가면, (0,0)으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 (0,0)에서 왼쪽으로 한 칸 걸어가면 위치 (0,M-1)에 도달할 것이다. 마찬가지로 준겸이가 (0,0)에서 위로 한 칸 걸어가면 (N-1, 0)에 도달하게 된다.

준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸에서 시작해, 숲에 막히지 않고 비어 있는 칸에 도달할 수 있다면 A와 B는 같은 구역이다. 반대로, 도달할 수 없다면 A와 B는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

 

유형 : BFS

 

접근 방식

• 평범한 그래프 탐색이지만 4분위 탐색을 위한 다음 좌표 계산에서 약간의 조정이 필요하다.
• 다음 좌표가 왼쪽으로 넘어가거나 오른쪽,위,아래로 넘어가는 경우 1,n,m으로 조정한다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int dx[] = {0,0,-1,1};
    static int dy[] = {1,-1,0,0};

    static int[][] board;
    static boolean[][] v;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        v = new boolean[n+1][m+1];

        for(int i=1;i<=n;i++){

            st = new StringTokenizer(bf.readLine(), " ");

            for(int j=1;j<=m;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0;

        for(int i=1;i<=n;i++){

            for(int j=1;j<=m;j++){

                if(board[i][j] == 0 && !v[i][j]){

                    v[i][j] = true;
                    go(i,j);
                    result += 1;
                }
            }
        }

        System.out.println(result);
        bf.close();
    }

    static void go(int x,int y){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));


        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1)
                    nx = n;

                else if(nx > n)
                    nx = 1;

                if(ny < 1)
                    ny = m;

                else if(ny > m)
                    ny = 1;


                if(board[nx][ny] == 1)
                    continue;

                if(!v[nx][ny]){
                    v[nx][ny] = true;
                    q.add(new Node(nx,ny));
                }
            }
        }
    }
}
class Node{
    int x;
    int y;

    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}