백준 알고리즘 1012 (유기농 배추) - C++, Python

[문제] 백준 알고리즘 1012 (유기농 배추)

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

1012번: 유기농 배추

 

2667번 단지번호붙이기와 비슷하다. (지난 풀이)

> https://wlstyql.tistory.com/86

백준 알고리즘 2667 (단지번호붙이기) - C++, Python

 

다른 점은, Map이 주어지는 것이 아니라, 좌표가 주어지면

그 좌표를 Map에 입력해 주어서 풀이하는 것이다. 이후 푸는 방식은 동일하다.

 

1. Map과 Visited 생성 & 초기화

2. 좌표를 받아서 Map에 1 표시

3. DFS 실행하며 stack

4. stack의 길이 출력

 

[C++]

#include <cstdio>
#include <algorithm> // sort
#include <cstring> // memest
#include <deque> // stack
using namespace std;

bool M[51][51];
bool visited[51][51];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };


int solve_dfs(int depth, int x, int y, int n, int m) {
	for (int i = 0; i < 4; i++) {
		int nx = 0, ny = 0;
		nx = x + dx[i];
		ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if (M[nx][ny] && !visited[nx][ny]) {
				visited[nx][ny] = 1;
				depth = solve_dfs(depth + 1, nx, ny, n, m);
			}
		}
	}
	return depth;
}

int main() {
	int T = 0; 
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		deque<int> stk;
		memset(M, 0, sizeof(M));
		memset(visited, 0, sizeof(visited));
		int n = 0, m = 0, k = 0;
		scanf("%d %d %d", &n, &m, &k);
		for (int i = 0; i < k; i++) {
			int ix = 0, iy = 0;
			scanf("%d %d", &ix, &iy);
			M[ix][iy] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (M[i][j] && !visited[i][j]) {
					visited[i][j] = 1;
					stk.push_back(solve_dfs(1, i, j, n, m));
				}
			}
		}
		printf("%d", stk.size());
		printf("\n");
	}
}

 

Python의 경우 sys.setrecursionlimit()로 재귀 함수 깊이 제한을 해제 해줘야

제출 시 오류가 안난다. 복잡하지 않은 알고리즘이라서 10**4 정도면 되는 것 같다.

 

[Python]

import sys
sys.setrecursionlimit(10**4)
T = int(sys.stdin.readline())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def solve_dfs(depth, x, y, n, m):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if M[nx][ny] and not visited[nx][ny]:
                visited[nx][ny] = True
                depth = solve_dfs(depth+1, nx, ny, n, m)
    return depth

for _ in range(T):
    n, m, k = map(int, sys.stdin.readline().split())
    stack = []
    M = [[False] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        ix, iy = map(int, input().split())
        M[ix][iy] = True
    for i in range(n):
        for j in range(m):
            if M[i][j] and not visited[i][j]:
                visited[i][j] = True
                stack.append(solve_dfs(0, i, j, n, m))
    print(len(stack))