[백준] 1012번 - 유기농 배추 (Java)(◎)

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

1012번: 유기농 배추

<문제 분석>

1. 지렁이는 상/하/좌/우로만 연결된 배추로만 이동할 수 있으니, 상하좌우로 연결된 배추군집의 수를 구하면 된다.

2. 입력형식이 배추의 좌표이므로 이를 받아서 인접배열로 구성한다.

 

 

<문제 풀이>

1. 상하좌우로 확장하면서 배추그룹을 만들면서 이동하면 된다.

2. dfs의 파라미터는 x, y 좌표를 넘겨준다.

3. 메인함수의 for문에서 1을 반견해서 dfs를 호출하면 새로운 그룹의 시작이므로 그때 count++를 해준다.

 

 

<주의>

1. 입력함수 처리할 때 메인함수에서 for 문을 돌려서 받는 처리를 하는 도중에 실수를 해서 좀 해멨음.

 

 

<구현 #1>

import java.util.*;

/*
백준 1012번 : 유기농 배추
*/

public class Main {
    static int N, M, K;
    static int A[][];
    static boolean visited[][];

    int num = 0;
    int count = 1;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    void DFS(int x, int y) {
        visited[x][y] = true;
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (visited[nx][ny]) continue;//방문한 정점이면 스킵
            if (A[nx][ny] == 0) continue;//값이 0이면 간선이 없으므로 스킵
            count++;
            DFS(nx, ny);
        }
    }

    void Solve() {
        visited = new boolean[N][M];
        num = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (A[i][j] == 0) continue;
                if (visited[i][j]) continue;
                DFS(i, j);// 새 단지 검색
                num++;// 단지 번호 업데이트
            }
        }
        System.out.println(num);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int i=0; i<T; i++) {
            M = in.nextInt();//배추밭 가로길이
            N = in.nextInt();//세로길이
            K = in.nextInt();//배추 개수
            A = new int[N][M];
            for (int j=0; j<K; j++) {
                int y = in.nextInt();
                int x = in.nextInt();
                A[x][y] = 1;
            }
            m.Solve();
        }
	}
}

 

<구현 #2 >

1. DFS -> BFS로 변경

2. Scanner-> BufferedReader로 변경

3. 방문처리를 visited[][] = true -> map[][] = 0로 변경

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

public class Main {
    static int T, N, M, K;
    static int map[][];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    class Node {
        int x, y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    void BFS(int x, int y) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(new Node(x, y));

        while (!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (map[nx][ny] == 0) continue;
                map[nx][ny] = 0;
                Q.offer(new Node(nx, ny));
            }
        }
    }
    
	int Solve() {
		int count = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 1) {
                    BFS(i, j);
                    count++;
                }
            }
        }
		return count;
	}

    public static void main(String[] args) throws Exception {
        int ans = -2;
        Main m = new Main();
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);

        T = Integer.parseInt(br.readLine());
        for (int t=0; t<T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            map = new int[N][M];
            
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int y = Integer.parseInt(st.nextToken()); // 가로축
                int x = Integer.parseInt(st.nextToken()); // 세로축
                map[x][y] = 1;
            }
            ans = m.Solve();// 여기서부터 작성
            System.out.println(ans); // 출력 하는 부분
        }
    }
}