백준 BOJ 1012번

---

접근 방법

인접한 배추들을 그래프 형태로 생각하면, DFS와 BFS를 사용하여 문제를 풀 수 있다.

DFS, BFS 둘다 그래프를 탐색하는 방법이다.

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조다.

그래프를 탐색한다는 것은 하나의 정점으로부터 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다.

 

그 중에 먼저 DFS부터 알아보자

 

깊이 우선 탐색 ( DFS, Depth-First Search )

→ 최대한 깊이 내려간 뒤에 더이상 깊은 곳이 없으면 옆으로 이동한다.

출처 https://developer-mac.tistory.com/64

위의 사진처럼 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 브랜치로 넘어가기 전에 현재 탐색 중인 브랜치를 완벽하게 탐색하는 방식이다.

 

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

 

 

다음은 bfs를 알아보자.

너비 우선 탐색 ( BFS, Breadth-First Search)

→ 인접한 노드를 먼저 탐색하는 방법

출처 https://developer-mac.tistory.com/64

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.

BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색한다.

 

DFS vs BFS

출처 : https://namu.wiki/w/BFS

DFS	BFS
재귀함수나 스택으로 구현	큐로 구현 (재귀적으로 동작 X) FIFO(선입선출)로 탐색

 

---

코드

문제는 dfs를 사용해서 풀었다.

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

public class Main{
    static int[][] field;
    static boolean[][] visit;
    static int M,N,K;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i < T; i++){
            M = sc.nextInt();
            N = sc.nextInt();
            K = sc.nextInt();
            field = new int[N][M];
            visit = new boolean[N][M];
            for(int j = 0; j < K; j++){
                field[sc.nextInt()][sc.nextInt()] = 1;
            }
            int count = 0;
            for(int x = 0; x < N; x++){
                for(int y = 0; y < M; y++){
                    if(field[x][y] == 1 && !visit[x][y]){
                        find(x,y);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
       
    }
    public static void find(int startX, int startY){
        visit[startX][startY] = true;
        int[] arrX = {-1, 1, 0, 0};
        int[] arrY = {0, 0, -1, 1};
        for(int i = 0; i < 4; i++){
            int x = startX + arrX[i];
            int y = startY + arrY[i];
            if(x >= 0 && x < M && y >= 0 && y < N) {
                if(field[x][y] == 1 && !visit[x][y]){
                    find(x, y);
                }
            }
        }
    }
}