[Java] 백준(실버-2) 1012번 - 유기농 배추

문제 풀이

---

이 문제는 BFS만 잘 숙지하고 있으면 너무 간단하게 풀 수 있다.

아이디어 도출

• 문제를 잘 보면 배추밭에 필요한 지렁이 개수는 연결노드의 개수와 같음을 알 수 있다.
• 결국, BFS 함수의 호출 횟수가 지렁이 개수가 된다.

BFS 문제 중에서도 상하좌우 탐색하면서 별다른 작업을 하지 않고 BFS 함수 호출 횟수만 세면 되기 때문에 생각보다 쉽게 풀었다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {
    // BFS에서 x, y좌표마다 상하좌우로 이동할 배열 선언
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    // 방문 배열로 사용할 2차원 배열 선언
    static boolean[][] visited;
    
    // 배추의 위치를 저장할 2차원 배열 선언
    static int[][] arr;

    // 배추밭의 크기를 결정할 N,M 선언
    static int N;
    static int M;
    
    // 배추밭에 필요한 지렁이 수를 구할 변수 선언
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());

        for(int idx=0; idx<T; idx++) {
            // 테스트케이스마다 N, M을 변경
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            
            // 배추밭을 그릴 2차원 배열 크기 N*M로 초기화
            arr = new int[N][M];
            // 방문배열 초기화
            visited = new boolean[N][M];
            
            // K만큼 배추 위치를 입력받음
            for(int idx2=0; idx2<K; idx2++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr[x][y] = 1;
            }
            
            // 연결 노드 개수가 곧 필요한 지렁이 개수가 됨.
            cnt = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    // BFS 호출 횟수가 지렁이 개수이다.
                    if(!visited[i][j] && arr[i][j] != 0) {
                        cnt++;
                        BFS(i,j);
                    }
                }
            }
            bw.write(cnt+"\n");
        }
        
        bw.close();
        br.close();
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<4; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(0<=i && 0<=j && i<N && j<M) {
                    if(arr[i][j] != 0 && !visited[i][j]) {
                        visited[i][j] = true;
                        q.add(new int[]{i, j});
                    }
                }
            }
        }

    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.