백준 1012번: 유기농 배추

[www.acmicpc.net/problem/1012]

#풀이

- dfs 알고리즘

1. dfs에서 stack이 비면 cabbage에 있는 값을 가져온다.

2. 가져온 값이 방문하지 않은 곳이면 worm을 1 올린다.

3. dfs를 시행하면서 방문하면 data = 0 을 한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

import sys input = lambda: sys.stdin.readline().rstrip() #print = sys.stdout.write #sys.stdin = open('input.txt', 'r')   for _ in range(int(input())):     x,y,n=map(int,input().split())       data=[[0 for _ in range(y)] for _ in range(x)]     cabbage=[tuple(map(int,input().split())) for _ in range(n)]       #배추 있는곳 1로 만들기     for a,b in cabbage:         data[a][b]=1       #상하좌우     dx=[0,0,1,-1]     dy=[1,-1,0,0]       stack=[]     worm=0       #dfs 알고리즘     while cabbage:         if not stack:             tmp1,tmp2=cabbage.pop()             if data[tmp1][tmp2] == 1:                 worm+=1                 stack.append((tmp1,tmp2))         while stack:             a,b=stack.pop()             data[a][b]=0             for i in range(4):                 da=a+dx[i]                 db=b+dy[i]                 if 0 <= da < x and 0 <= db < y:                     if data[da][db] == 1:                         stack.append((da,db))     print(worm)   Colored by Color Scripter

cs