[백 준/DFS/BFS] 1012: 유기농 배추

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

1012번: 유기농 배추

핵심 아이디어

• DFS 탐색 알고리즘을 통해 풀 수 있는 문제, BFS로도 가능. O(N) 시간 복잡도
• X -> M과 매치, Y -> N과 매치되는것에 주의! 

풀이

dfs는 기본적으로 스택자료구조를 기반으로 재귀함수를 통해 구현됩니다. dfs를 구현하는 방식은 여러가지가 있는데 그 중 두 가지 방식을통해 구현하였습니다.

import sys
sys.setrecursionlimit(10000)

def dfs(x,y):
	#만약 주어진 범위를 벗어나는 경우 즉시 종료
	if x < 0 or x >=n or y < 0 or y >= m:
		return False
	if graph[x][y] == 1:
		graph[x][y] = 0
		#현재 위치에서 재귀적으로 반복
		dfs(x-1,y)
		dfs(x+1,y)
		dfs(x, y-1)
		dfs(x, y+1)
		return True
	return False

t = int(input())
for _ in range(t):
	m, n, k = map(int, input().split())

	# 2차원 배열을 미리 선언해서 풀기
	graph = [[0]*m for _ in range(n)]
	for _ in range(k):
		x, y = map(int, input().split())
		graph[y][x] = 1

	count = 0
	for i in range(n):
		for j in range(m):
			if dfs(i,j) == True:
				count += 1
	print(count)

dfs를 구현하는 또 다른 방식은 다음과 같습니다.

# 재귀 limit 설정
import sys
sys.setrecursionlimit(10000)

### 2
# dfs 정의
def dfs(x, y):
    # 상하좌우 확인을 위해 dx, dy 생성
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    # 네 방향 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < M) and (0 <= ny < N):  # nx:ny ↔ M:N 범위 참고
            if graph[ny][nx] == 1:
                graph[ny][nx] = -1  # 배추가 인접할 때 체커
                dfs(nx, ny)

import sys
sys.setrecursionlimit(10000)

이 때 주의할 점이 있습니다. 이 코드는 재귀의 한도를 풀어주는 함수이다. 만약 재귀를 사용해서 풀어야 하는 문제라면, 해당 코드는 습관적으로 사용하는 것이 좋습니다. 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 되는데, 문제는 코딩테스트 환경에서는 에러메세지를 볼 수 없다는 것이다. 그러므로 함정에 빠지지 않기 위해 재귀함수를 사용한다면 잊지말고 꼭 써주어야 합니다.

다른 풀이

'''
배추흰지렁이는 배추 근처에 서식하며 해충을 잡아 먹는다.
어떤 배추에 배추 흰지렁이가 한 마리라도 살고 있으면 인접한 다른 배추로
이동 가능해서 보호 가능 -> 상하좌우 인접

DSF 탐색 알고지름 활용
'''


import sys
sys.setrecursionlimit(10**6)
t = int(input())
for _ in range(t):
	m,n,k = map(int, input().split())
	# 맵 초기화
	graph = [[0] * m for _ in range(n)]
	for _ in range(k):
		x,y = map(int, input().split()) # 열 행
		graph[y][x] = 1
	# dfs 탐색 알고리즘 활용
	def dfs(y,x):
		if y < 0 or y >=n or x < 0 or x >=m:
			return False
		if graph[y][x] == 1: # 배추가 있는 곳이라면
			graph[y][x] = 0 # 방문 처리
			# 모든 위치를 재귀적으로 탐색 상 하 좌 우
			dfs(y-1,x)
			dfs(y+1,x)
			dfs(y,x-1)
			dfs(y,x+1)
			return True
		return False
	cnt = 0
	for i in range(n):
		for j in range(m):
			if dfs(i,j) == True:
				cnt += 1
	print(cnt)

C++ 코드

#include <iostream>

using namespace std;

int t, x,y,n, m, k;
int graph[50][50];

// DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
bool dfs(int y, int x) {
	// 주어진 범위를 벗어나는 경우 즉시 종료
	if (y < 0 || y >= n || x < 0 || x >= m) {
		return false;
	}

	// 현재 위치가 배추가 심어져 있는 위치라면
	if (graph[y][x] == 1) {
		graph[y][x] = -1; // 방문처리
		// 상 하 좌 우 위치들도 모두 재귀적으로 호출
		dfs(y-1,x);
		dfs(y+1,x);
		dfs(y,x-1);
		dfs(y,x+1);
		return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// 테스트 케이스 개수 입력받기
	cin >> t;
	for (int q = 0; q < t; q++) {
		// 격자 크기, 배추 위치 개수
		cin >> m >> n >> k;
		// 맵 초기화
		memset(graph, 0, sizeof(graph));

		for (int i = 0; i < k; i++) {
			cin >> x >> y; // 열 행 입력받기
			graph[y][x] = 1; // 배추 심기
		}

		// 모든 위치에 대하여
		int result = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (dfs(i,j) == true) {
					result++; // result += 1;
				}
			}
		}
		cout << result << '\n';
	}
	return 0;
}