문제링크: https://www.acmicpc.net/problem/1012
간단한 graph 문제이다. dfs함수를 이용하여 재귀용법으로 풀었다.
import sys
sys.setrecursionlimit(10**6)
visited = []
dir_go = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
def dfs(array_list,y,x):
if [y,x] in visited:
return
visited.append([y,x])
for i in range(4):
x_1= x + dir_go[i][0]
y_1 = y + dir_go[i][1]
if x_1 >= 0 and x_1 <= len(array_list[0]) -1 and y_1 >=0 and y_1 <= len(array_list) -1 and array_list[y_1][x_1] == 1:
dfs(array_list,y_1,x_1)
T = int(sys.stdin.readline())
for _ in range(T):
M, N, K = map(int,sys.stdin.readline().split())
array_list = [[0]* M for _ in range(N)]
for _ in range(K):
x , y = map(int,sys.stdin.readline().split())
array_list[y][x] = 1
for i in range(N):
for j in range(M):
if array_list[i][j] == 1 and [i,j] not in visited:
cnt += 1
dfs(array_list,i,j)
print(cnt)
cnt = 0
visited.clear()