백준 1012번 -유기농 배추

BFS와 DFS 모두 활용할 수 있는 연습문제라고 생각하면 된다.

 

너비 우선 탐색(BFS)을 사용하는 이유

1. 최단 경로 탐색에 유리하다.
   BFS는 탐색을 가까운 노드부터 순차적으로 넓혀가며 수행하기 때문에, 시작 지점에서 특정 목표 지점까지의 최단 경로를 찾을 때 유리하다. 예를 들어 미로 탐색에서 출발점에서 도착점까지의 최단 경로를 찾을 때, BFS는 가장 먼저 목표 지점에 도달하는 경로가 최단 경로가 되므로 이를 바로 반환할 수 있다.
2. 모든 노드를 고르게 탐색한다.
   BFS는 한 지점에서 출발하여 깊이를 하나씩 늘리며 탐색하므로, 모든 노드를 고르게 탐색한다. 모든 인접 노드들을 차례로 확인하며 탐색하므로 특정 노드들이 더 깊게 우선 탐색되는 일이 없다. 이 점은 깊이 우선 탐색(DFS)과 다르며, 특히 그래프가 넓게 퍼져 있는 경우 탐색 효율성이 좋다.
3. 레벨 순서 탐색(계층적 탐색)에 적합하다.
   BFS는 탐색 깊이(레벨)가 동일한 노드들끼리 탐색하기 때문에, 트리나 그래프의 각 레벨을 순차적으로 탐색할 때 적합하다. 예를 들어 조직 구조, 계층적 관계, 연결된 네트워크에서 각 레벨별로 노드를 탐색해야 할 때 유리하다.
4. 고립된 노드를 탐색할 필요가 없을 때 유리하다.
   BFS는 목표 지점에 도달하면 즉시 탐색을 종료할 수 있어, 목표가 특정 노드에 도달하는 것이라면 효율적이다. 예를 들어 SNS 네트워크 상에서 특정 사람과 몇 다리 건너 연결되는지 확인할 때, BFS는 가장 가까운 연결을 먼저 탐색하므로 빠르게 목표에 도달할 수 있다.
5. DFS보다 재귀 깊이 문제에서 유리하다.
   BFS는 주로 큐를 사용하여 탐색하기 때문에, 깊이 우선 탐색(DFS)에서 발생할 수 있는 재귀 깊이 문제가 없다. 따라서 깊이가 깊거나 노드가 많은 경우에도 메모리 초과 없이 안정적으로 탐색할 수 있다.

BFS가 적합한 문제 유형은 다음과 같다:

• 최단 경로 문제: 미로, 최단 거리 탐색, 경로 찾기 등
• 레벨별 탐색 문제: 트리의 레벨 순회, 계층적 데이터 구조 탐색
• 그래프 탐색에서 특정 조건을 만족하는 첫 번째 노드를 찾는 문제

BFS 동작 흐름

1. 시작 노드 방문 및 큐에 삽입한다.
   탐색을 시작할 시작 노드를 방문 처리하고 큐에 넣는다. 이 큐는 탐색할 노드를 관리하는 역할을 한다.
2. 큐에서 노드를 꺼내 현재 노드로 설정한다.
   큐가 비어있지 않은 동안 반복하며, 큐의 맨 앞에 있는 노드를 꺼내서 현재 노드로 설정한다.
3. 인접 노드를 확인하고 방문한다.
   현재 노드에 연결된 인접 노드들을 하나씩 확인한다. 각 인접 노드에 대해 아직 방문하지 않은 노드라면 방문 처리하고 큐에 추가한다.
4. 반복하며 탐색을 종료한다.
   위 과정을 큐가 빌 때까지 반복하며, 큐가 비어 있으면 탐색이 완료된다.

import sys
from collections import deque

input = sys.stdin.readline  # 빠른 입력을 위한 설정

# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 함수 정의 (i, j는 시작 좌표)
def bfs(i, j, graph, visited):
    queue = deque([(i, j)])  # 시작 위치를 큐에 추가
    visited[i][j] = 1  # 시작 위치를 방문 처리

    while queue:
        x, y = queue.popleft()  # 큐에서 현재 위치를 꺼냄
        # 상하좌우 방향으로 인접한 위치를 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]  # 다음 위치 계산
            # 격자 범위 내에 있고, 아직 방문하지 않았으며, 배추가 심어진 경우
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and visited[nx][ny] == 0 and graph[nx][ny] == 1:
                visited[nx][ny] = 1  # 방문 처리
                queue.append((nx, ny))  # 다음 위치를 큐에 추가하여 탐색

# 테스트 케이스 수 입력
tc = int(input())
for _ in range(tc):
    m, n, k = map(int, input().split())  # 가로(m), 세로(n), 배추 개수(k)
    
    # 배추밭과 방문 여부를 저장할 배열 초기화
    graph = [[0 for _ in range(m)] for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    c = 0  # 필요한 배추흰지렁이 수 (군집 수)

    # 배추가 심어진 위치를 그래프에 표시
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1  # (y, x) 위치에 배추 표시

    # 배추밭 전체를 돌면서 BFS로 군집 찾기
    for i in range(n):
        for j in range(m):
            # 배추가 있고 아직 방문하지 않은 위치라면 새로운 군집으로 간주
            if graph[i][j] == 1 and visited[i][j] == 0:
                bfs(i, j, graph, visited)  # 새로운 군집에 대해 BFS 수행
                c += 1  # 새로운 군집을 발견했으므로 지렁이 수 증가

    print(c)  # 각 테스트 케이스마다 필요한 배추흰지렁이 수 출력

 

깊이 우선 탐색(DFS)을 사용하는 이유

1. 모든 경로를 탐색하는 데 유리하다.
   DFS는 한 방향으로 갈 수 있을 때까지 끝까지 탐색하고, 막히면 되돌아와 다른 경로를 탐색한다. 이 방식은 모든 가능한 경로를 찾거나 탐색해야 하는 문제에서 매우 유용하다. 예를 들어 경로의 모든 조합을 확인해야 하는 문제에서 DFS는 필요한 모든 경우를 탐색할 수 있다.
2. 백트래킹 문제에 적합하다.
   DFS는 백트래킹(backtracking) 문제를 해결하는 데 매우 유리하다. 백트래킹은 특정 조건을 만족하지 않으면 그 경로를 되돌아가는 방식으로 최적의 답을 찾는 알고리즘이다. 예를 들어 미로 탈출, 퍼즐 문제, 조합 생성 문제 등에서 특정 조건을 만족할 때까지 깊이 탐색하고, 조건을 만족하지 않으면 되돌아가 다른 경로를 탐색할 수 있다. DFS는 이 과정을 자연스럽게 구현할 수 있다.
3. 재귀를 이용해 구현하기 쉽다.
   DFS는 스택 자료구조를 사용하는데, 재귀 호출이 내부적으로 스택을 사용하기 때문에 DFS를 구현할 때 재귀 함수로 간단하게 구현할 수 있다. 이러한 재귀 방식은 코드의 간결성과 가독성을 높이는 데 유리하다. 따라서 재귀 호출이 편리한 문제에서는 DFS가 많이 사용된다.
4. 메모리 효율성이 높다.
   넓고 얕은 그래프나 트리에서는 BFS가 적합할 수 있지만, 반대로 깊이가 깊은 그래프나 트리에서는 DFS가 메모리를 절약할 수 있다. BFS는 탐색 깊이가 깊을 때 큐에 많은 노드를 유지해야 하지만, DFS는 길게 이어진 경로만 탐색하면 되므로 메모리 사용량이 적다.

DFS가 적합한 문제 유형은 다음과 같다:

• 경로와 경로 조합을 찾는 문제: 모든 가능한 경로를 탐색해야 할 때
• 백트래킹 문제: 조합, 순열, 미로 탐색, 퍼즐 문제 등
• 트리 구조 탐색: 트리의 특정 경로나 노드 조합을 찾을 때

DFS는 특정 경로를 끝까지 탐색하고 필요한 경우 되돌아가는 방식으로 문제를 해결하므로, 모든 가능한 조합을 탐색하거나 조건을 만족하는 경우를 찾고, 만족하지 않으면 되돌아가서 탐색을 이어가는 문제에 매우 적합하다.

DFS(깊이 우선 탐색)의 동작 흐름

1. 시작 노드를 방문 처리한다.
   탐색을 시작할 시작 노드를 방문 처리하고, 이 노드에서 갈 수 있는 다음 노드로 이동을 시도한다.
2. 인접 노드를 탐색하고 재귀 호출한다.
   현재 노드의 인접 노드들을 하나씩 탐색한다. 아직 방문하지 않은 인접 노드가 있으면 해당 노드를 방문 처리하고, 그 위치에서 DFS를 재귀적으로 호출하여 현재 탐색 중인 경로의 다음 깊이로 이동한다.
3. 재귀 호출에서 돌아오며 백트래킹을 수행한다.
   더 이상 인접 노드로 이동할 수 없는 상황(끝까지 도달했거나, 이미 방문된 노드뿐일 때)이 되면 재귀 호출이 종료되며 이전 단계로 돌아온다. 이전 위치로 되돌아오면, 다음 인접 노드가 있다면 그 노드를 탐색하고, 없다면 또다시 이전 위치로 돌아간다.
4. 탐색이 완료되면 종료한다.
   시작 지점에서 DFS 호출이 완료되면 탐색이 종료된다. 이 과정을 반복하여 그래프의 모든 노드를 방문할 때까지 탐색한다.

import sys
sys.setrecursionlimit(10000)  # 재귀 호출 제한을 늘려서 깊은 DFS 탐색이 가능하도록 설정
input = sys.stdin.readline  # 빠른 입력을 위한 설정

# 상하좌우 이동을 위한 방향 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 깊이 우선 탐색(DFS) 함수 정의
def dfs(i, j, graph, visited):
    visited[i][j] = 1  # 현재 위치 방문 처리
    # 상하좌우 네 방향으로 탐색
    for _ in range(4):
        nx, ny = i + dx[_], j + dy[_]  # 다음 위치 계산
        # 격자 범위 내에 있고, 배추가 심어져 있으며, 방문하지 않은 위치일 경우
        if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] == 1 and visited[nx][ny] == 0:
            dfs(nx, ny, graph, visited)  # 재귀적으로 DFS 탐색

# 테스트 케이스 수 입력
tc = int(input())
for _ in range(tc):
    # 각 테스트 케이스마다 배추밭 정보 입력
    m, n, k = map(int, input().split())  # m: 가로 길이, n: 세로 길이, k: 배추 위치 개수
    graph = [[0 for i in range(m)] for j in range(n)]  # 배추밭을 나타내는 2차원 리스트 초기화
    visited = [[0 for i in range(m)] for j in range(n)]  # 방문 여부를 기록할 리스트 초기화
    c = 0  # 필요한 배추흰지렁이 수 (군집 수)

    # 배추 위치 입력받아 배추밭에 표시
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1  # 배추가 심어진 위치를 1로 표시

    # 배추밭 전체를 순회하며 DFS로 군집을 탐색
    for i in range(n):
        for j in range(m):
            # 배추가 있고 방문하지 않은 경우 새로운 군집으로 간주
            if graph[i][j] == 1 and visited[i][j] == 0:
                dfs(i, j, graph, visited)  # 새로운 군집에 대해 DFS 수행
                c += 1  # 군집을 찾았으므로 지렁이 수 증가

    print(c)  # 현재 테스트 케이스의 결과 출력 (필요한 배추흰지렁이 수)