[Python] 백준 #1012 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

처음부터 반례까지 모두 찾아내고, 한번에 '성공!'을 받아내는걸 목표로 하고 있는 요즘.

문제 완벽하게 이해하고 반례를 찾아내는게 키포인트다.

꼼꼼하게 집중해서.!

 

DFS로 한번에 해결~

from collections import deque
que=deque()

dx=[-1,1,0,0]
dy=[0,0,-1,1]

result=[]
t=int(input())

for i in range(t): #테스트 케이스
    cnt=0
    
    #배추 정보 입력받기
    n,m,k=map(int,input().split())
    graph=[[] for i in range(n)]
    
    #배추 초기화   
    for i in range(n):
        for j in range(m):
            graph[i].append(0)
        
    for j in range(k): #배추 자리
        x,y=map(int,input().split())
        graph[x][y]= 1 #배추심기
    
    for q in range(n):
        for w in range(m):
            if(graph[q][w]==1):
                que.append([q,w])
                graph[q][w]=0 #체크한건 0으로
                while(que):
                    p=que.pop()
                    x=p[0]
                    y=p[1]
                    
                    #상하좌우 체크
                    for e in range(4):
                        xx=x+dx[e]
                        yy=y+dy[e]
                        
                        #벗어나는 경우 제외
                        if(xx>=0 and xx<n and yy>=0 and yy<m):
                            if(graph[xx][yy]==1):
                                que.append([xx,yy])
                                graph[xx][yy]=0 #체크한건 0으로
                
                cnt+=1
                
    result.append(cnt)            

for i in result:
    print(i)