[백준] 유기농 배추

출처:: www.acmicpc.net/problem/1012

분류:: DFS

 

1. 문제 이해 및 해결과정

-DFS가 몇번 호출되는 가를 묻는 전형적인 문제

 

2. 풀이방법

-dfs

#if 01
//유기농 배추
// https://www.acmicpc.net/problem/1012
#include <iostream>
#include <cstring> //memset
#define MAXN (50)
using namespace std;
int T, M, N, K;
int map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
int dh[] = { -1,1,0,0 };
int dw[] = { 0,0,-1,1 };
void DFS(int h, int w) {

	visited[h][w] = 1;

	for (int i = 0; i < 4; i++) {
		int nh = h + dh[i];
		int nw = w + dw[i];

		if (visited[nh][nw] == 1 || map[nh][nw] == 0)continue;
		if (nh < 0 || nw < 0 || nh >= N || nw >= M)continue;

		DFS(nh,nw);
	}

}
void InputData() {

	scanf("%d", &T);

	for (int t = 0; t < T; t++) {
		int sol = 0;
		scanf("%d %d %d", &M, &N, &K);

		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));

		for (int k = 0; k < K; k++){
			int x, y;
			scanf("%d %d", &x, &y);
			map[y][x] = 1;
		}

		for (int i = 0; i < N; i++) {//세로
			for (int j = 0; j < M; j++) { //가로
				if (map[i][j] == 1 && visited[i][j] == 0) {
					DFS(i, j);
					//printf("%d %d\n", i, j);
					sol++;
				}
			}
		}
		printf("%d\n", sol);
	}
}
int main() {

	freopen("input.txt", "r", stdin);
	InputData();


	return 0;
}
#endif

2. python

#유기농 배추
#https://www.acmicpc.net/problem/1012
import sys
sys.stdin = open("input.txt","r")
sys.setrecursionlimit(50000)

t=int(input())
dh=[-1,0,1,0]
dw=[0,1,0,-1]

def dfs(h,w):
    visited[h][w]=True
    for i in range(4):
        nh=h+dh[i]
        nw=w+dw[i]
        if 0<=nh<n and 0<=nw<m and visited[nh][nw]==False and board[nh][nw]==1:
            dfs(nh,nw)
            visited[nh][nw]=True

while t>0:
    m,n,k=map(int,input().split()) #가로, 세로
    board = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        w,h=map(int,input().split())
        board[h][w]=1

    cnt=0
    for i in range(n):
        for j in range(m):
            if board[i][j]==1 and visited[i][j]==False:
                dfs(i,j)
                cnt+=1
    print(cnt)
    t-=1

 

3. 오답원인

-testcase가 여러개인데 visited 배열 초기화를 안함 

 

4. 알게된 점

-테스트 케이스가 여러개일때 배열 초기화 되어있는지 항상 확인

-memset 은 cstring 

sys.setrecursionlimit(10000)

- 파이썬은 재귀가 1000까지만 돌아서 깊이 설정을 해주어야함