[BOJ] 1012 유기농 배추

import collections
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(n):
    que=collections.deque()
    que.append(n)
    while que:
        t=que.popleft()
        ax=t//1000000
        ay=t%1000000
        visit[ax][ay]=0
        for i in range(4):
            nx=ax+dx[i]
            ny=ay+dy[i]
            if 0<=nx<M and 0<=ny<N:
                if arr[nx][ny]==1 and visit[nx][ny]==-1:
                    que.append(1000000*nx+ny)
                    visit[nx][ny]=0
    return
 
 
T=int(input())
 
for tc in range(1,T+1):
    N,M,K=list(map(int,input().split()))
    arr=[[0 for j in range(N)] for i in range(M)]
    visit=[[-1]*N for i in range(M)]
    
    for _ in range(K):
        y,x=list(map(int,input().split()))
        arr[x][y]=1
    cnt=0
    for i in range(M):
        for j in range(N):
            if arr[i][j]==1 and visit[i][j]==-1:
                cnt+=1
                bfs(i*1000000+j)
    print(cnt)
    

 

 

 

위의 방식은 BFS를 이용해서 푼 방식이다.

 

 

dx=[1,-1,0,0]
dy=[0,0,1,-1]
import sys
sys.setrecursionlimit(10**6)
def dfs(x,y,_cnt):
    dist[x][y]=_cnt
 
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] and dist[nx][ny]==-1:
                dfs(nx,ny,_cnt)
 
 
 
 
t=int(input())
for _ in range(t):
    M,N,K=map(int,input().split())
    arr=[[0 for col in range(M)] for row in range(N)]
    dist=[[-1 for col in range(M)] for row in range(N)]
    for _ in range(K):
        y,x=map(int,input().split())
        arr[x][y]=1
    
    cnt=0
 
    for i in range(N):
        for j in range(M):
            if arr[i][j]==1 and dist[i][j]==-1:
                cnt+=1
                dfs(i,j,cnt)
    print(cnt)
 

DFS를 이용한 방식이다.

 

BFS나 DFS로 풀면 되는 문제이다. 방문한적이 없고 서로 연결된 것들의 개수를 구하면 되는 문제이다.