[쇼미더코드 3회] 백준 27211 - 도넛 행성 (자바 java)

 문제 : boj27211

---

 

필요 알고리즘 개념

• BFS (너비 우선 탐색)
  
  • 약~간 응용된 BFS 문제이다.

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

 

---

 

풀이

  BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS 글'을 참고해보자.

 

  사실 위 글을 이해했다면 그냥 BFS와 다를바가 없다. 그냥 NxM 사이즈를 넘어갔을 때, 반대편으로 이동만 가능하도록 해두면 된다. 입력으로 주어진 지도 정보를 가로세로 3배씩 동일하게 반복해서 진행해도 될테지만, 일반적인 BFS에서 코드적으로 다음과 같이 반대편으로 돌리는 로직만 추가하면 해결 가능하다.

for (int d = 0; d < 4; d++) {
    int nr = cr+DR[d];	// nr은 다음번에 이동할 행의 좌표
    int nc = cc+DC[d];	// nc는 다음번에 이동할 열의 좌표
    if (nr<0) nr+=r;	// 음수라면 반대편으로 넘어가야하니 N을 더해준다(r이 입력으로 주어진 N임)
    if (nc<0) nc+=c;	// 마찬가지
    nr%=r;	// N을 넘어갔을 경우 반대편으로 다시 돌려야 한다.
    nc%=c;	// 마찬가지

    if (!map[nr][nc]) continue;	// 방문한곳이 아니라면
    map[nr][nc] = false;	// 방문체크
    q.add(new int[]{nr,nc});	// 큐에 추가
}

 

 

---

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[] DR = {0,0,-1,1};
    private static final int[] DC = {-1,1,0,0};
    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        boolean[][] map = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                if (Integer.parseInt(st.nextToken()) == 0)
                    map[i][j] = true;
            }
        }

        int answer = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (!map[i][j]) continue;
                answer++;
                Queue<int[]> q = new ArrayDeque<>();
                q.add(new int[]{i,j});
                map[i][j] = true;
                while (!q.isEmpty()) {
                    int cr = q.peek()[0];
                    int cc = q.poll()[1];
                    for (int d = 0; d < 4; d++) {
                        int nr = cr+DR[d];
                        int nc = cc+DC[d];
                        if (nr<0) nr+=r;
                        if (nc<0) nc+=c;
                        nr%=r;
                        nc%=c;

                        if (!map[nr][nc]) continue;
                        map[nr][nc] = false;
                        q.add(new int[]{nr,nc});
                    }
                }
            }
        }
        System.out.println(answer);
    }

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