-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1012BFS.py
More file actions
46 lines (36 loc) · 1.04 KB
/
Copy path1012BFS.py
File metadata and controls
46 lines (36 loc) · 1.04 KB
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
41
42
43
44
45
46
# 구글 검색
from collections import deque
from sys import stdin
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
t = int(input()) # 테스트케이스 2개
result_list = []
def make_graph(m, n, k):
graph = [[0] * m for _ in range(n)]
for _ in range(k):
x, y = map(int, stdin.readline().split())
graph[y][x] = 1
return graph
def bfs(y, x):
queue = deque([])
queue.append([y, x])
while queue:
y, x = queue.pop()
for d in range(4):
xx = dx[d] + x
yy = dy[d] + y
if 0 <= xx < m and 0 <= yy < n:
if graph[yy][xx] == 1:
graph[yy][xx] = 0
queue.append([yy, xx])
for _ in range(t):
result = 0
m, n, k = map(int, stdin.readline().split()) # m:가로, n:세로
graph = make_graph(m, n, k)
for i in range(n): # 세로
for j in range(m): # 가로
if graph[i][j] == 1:
bfs(i, j)
result += 1
result_list.append(result)
print(*result_list, sep='\n')