[백준, Java] 27211번, 도넛 행성(BFS)

문제 링크

27211번: 도넛 행성

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N x M 칸의 도넛 모양의 행성이 준겸이가 살고 있습니다.

2. 준겸이는 상하좌우로 이동할 수 있으며, 행과 열에 대해서 0과 {N-1, M-1}이 연결되어 있습니다.

3. 행성에는 숲이 존재하며, 해당 공간에는 접근하지 못합니다.(숲 : 1, 빈 땅 : 0)

4. 준겸이는 연결된 빈 땅을 탐색할 때 구역의 개수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS을 통해서 빈 땅을 탐험할 수 있는 구역을 탐색합니다.

 

3. 탐색을 통해 얻은 구역의 개수를 결과로 출력합니다.

 

 

도넛 행성 구역 탐색하기(BFS)

 

준겸이는 상하좌우로 이동할 수 있습니다.

 

	(-1, 0)
(0, -1)	준겸	(0, 1)
	(1, 0)

 

BFS을 진행해야 하는 경우.

 

준겸이가 탐색을 진행하려면 빈 땅(0)이어야 하며, 다른 구역에 포함되지 않아야 합니다.

 

다른 구역에 포함되는 것은 boolean[][]을 통해서 저장할 수 있습니다.

 

 

아래 도넛 행성을 준겸이가 탐색할 때에 시작할 수 있는 빈 땅

 

0	0	1
1	1	1
1	0	0

 

 

 

또한, (0, 0) 빈 땅을 탐색할 때 (0, 1)을 탐색하게 되기 때문에 boolean[0][1] = true 변경되면서 다음 구역 탐색 시작 지점으로는 선택되지 않게됩니다.

 

추가적으로 이 문제에서 신경써야 하는 요소가 1개 있습니다.

 

{N-1, 0}, {0, M-1}이 연결되어 있다는 것입니다.

 

 

(0, 0)에서 ←(왼쪽)으로 이동하면 (0, M-1)의 공간으로 이동하게 됩니다.

 

(0, 0)에서 ↓(아래)으로 이동하면 (N-1, 0)의 공간으로 이동하게 됩니다.

 

 

즉, 2가지 경우로 나눠집니다.

 

이동하려는 행과 열의 공간 < 0 일 때

 

행 : N-1, 열 : M-1 변경됩니다.

 

이동하려는 행과 열의 공간이 ≤ {N, M}일 때 

 

행 : y % N, 열 : x % N 변경됩니다.

 

  

 

 

결과적으로 BFS을 진행할 때마다 구역이 정해지기 때문에 결과로 출력해야 하는 값은 아래와 같습니다.

 

BFS을 돌리는 횟수 = 준겸이가 빈 땅의 구역을 탐색한 개수(결과)

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 5

 

M = 6

 

[도넛 행성]

 

1	1	1	1	1	1
1	0	0	0	1	1
1	1	1	1	0	0
1	1	1	1	0	0
1	1	1	1	1	1

 

2. BFS을 통해서 빈 땅을 탐험할 수 있는 구역을 탐색합니다.

 

구역에 포함되지 않은 빈 땅 BFS 진행

 

 

(1, 1) 빈 땅 BFS 탐색 진행

 

1	1	1	1	1	1
1	0	0	0	1	1
1	1	1	1	0	0
1	1	1	1	0	0
1	1	1	1	1	1

 

[BFS 탐색 결과]

 

1	1	1	1	1	1
1	0	0	0	1	1
1	1	1	1	0	0
1	1	1	1	0	0
1	1	1	1	1	1

 

(3, 4) 빈 땅 BFS 탐색 진행

 

1	1	1	1	1	1
1	0	0	0	1	1
1	1	1	1	0	0
1	1	1	1	0	0
1	1	1	1	1	1

 

[BFS 탐색 결과]

 

1	1	1	1	1	1
1	0	0	0	1	1
1	1	1	1	0	0
1	1	1	1	0	0
1	1	1	1	1	1

 

 

3. 탐색을 통해 얻은 구역의 개수를 결과로 출력합니다.

 

BFS 진행 횟수 2번 = 구역의 개수

 

 

2 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 도넛 행성의 정보를 띄어쓰기 기준 나누었습니다.
•  빈 땅이면서 다른 구역에 포함되지 않은 공간을 기준으로 BFS을 통해 구역을 탐색합니다.
• 모든 탐색이 끝났을 때 구역의 개수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs함수는 BFS을 통해서 빈 땅의 구역을 탐색합니다.
• bfs함수는 빈 땅을 방문하면 구역으로 확인하기 위해서 vistied[][]배열의 값을 true 변경합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //도넛 행성 구역 정보
    static class Pos{
        //r : 행, c : 열
        int r, c;
        Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //상하좌우 행, 열 변경 값
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    //도넛 행성 정보
    static int[][] map;
    //도넛 행성 빈 땅 구역 방문 정보
    static boolean[][] visited;
    static int N, M;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[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());
            }
        }
        visited = new boolean[N][M];
        int result = 0;
        //구역에 포함되지 않은 빈 땅 BFS 통한 탐색 진행
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                //빈 땅이면서, 다른 구역에 포함되지 않을 때
                if(map[i][j] == 0 && !visited[i][j]){
                    bfs(i, j);
                    //BFS 진행 횟수 ++ = 구역 개수 ++
                    result++;
                }
            }
        }
        //구역 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해 준겸이의 탐색 진행
    static void bfs(int r, int c){
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(new Pos(r, c));
        //시작 지점 구역 방문 처리
        visited[r][c] = true;
        //BFS 탐색 진행
        while(!q.isEmpty()){
            Pos cur = q.poll();
            //상하좌우 준겸이 이동 진행
            for(int i=0;i<4;i++){
                //준겸이가 이동했을 때 다음 구역 계산
                int nr = cur.r + dr[i] < 0 ? N-1 : (cur.r + dr[i]) % N;
                int nc = cur.c + dc[i] < 0 ? M-1 : (cur.c + dc[i]) % M;
                //구역에 속하지 않은 빈땅일 때 방문!
                if(!visited[nr][nc] && map[nr][nc] == 0){
                    visited[nr][nc] = true;
                    q.offer(new Pos(nr, nc));
                }
            }
        }
    }
}