[백준] no1012: 유기농 배추

문제

T : 테스트 케이스 수

M N Init : 가로길이 세로길이 배추가_있는_좌표개수

배추(1)가 뭉쳐있는 영역의 개수를 구하시오. (1이 완전히 0으로 사방이 둘러쌓인 형태 == 바둑)

 

문제 링크 : https://www.acmicpc.net/problem/1012

---

원리

BFS와 DFS 모두 접근이 가능하다.

---

풀이방법

BFS

1. static 변수를 지정한다. (BFS에서 사용하기 위함)

  1) 가로 세로 길이를 받을 M, N

  2) 상하좌우 이동을 만들어줄 int[] 두 개

  3) 배추심을 땅 groud[][]

  4) 방문 체크용 visited[][]

2. 입력을 통해 배추를 다 심는다

3. BFS를 돌면서 방문체크를 하여 재방문 하지 않도록 하며, 한 점에 대해 인접한 배추를 모두 탐색하면 count+1 해준다.

4. 모든 좌표에 대해 BFS를 순회해준다(단, 3에서 체크한 visited를 통해 방문한 곳은 방문하지 않는다)

---

나의 코드

1. BFS [ 15928kB | 168ms ]

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no1012 {

    static int N;
    static int M;
    static int[] horX = {1, -1, 0, 0};
    static int[] verY = {0, 0, 1, -1};
    static int[][] ground;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        while (T-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int init = Integer.parseInt(st.nextToken());
            ground = new int [N][M];
            for(int i=0; i<init ; i++) {
                StringTokenizer temp = new StringTokenizer(br.readLine());
                int nowM = Integer.parseInt(temp.nextToken());
                int nowN = Integer.parseInt(temp.nextToken());
                ground[nowN][nowM] = 1;
            }

            int count= 0;
            visited = new boolean[N][M];

            for(int i =0; i<N ; i++) {
                for(int j =0; j<M ; j++) {
                    if(ground[i][j]==1 && !visited[i][j]) {
                        BFS(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    private static void BFS(int nowI, int nowJ) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(nowI, nowJ));

        while(!dq.isEmpty()) {
            Node now = dq.poll();
            visited[now.Y][now.X] = true;

            for(int dir=0 ; dir<4 ; dir++) {
                int nowY = now.Y + verY[dir];
                int nowX = now.X + horX[dir];

                if(nowX >=0 && nowX <M && nowY >=0 && nowY < N) {
                    if (ground[nowY][nowX] == 1 && !visited[nowY][nowX]) {
                        dq.add(new Node(nowY, nowX));
                        visited[nowY][nowX] = true;
                    }
                }
            }
        }
    }

    static class Node {
        private int Y;
        private int X;

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

 

---

레퍼런스 코드

참고 링크 : https://1-7171771.tistory.com/59