링크





문제 요약:

배추 위치를 탐색하여 그 경로에 넣을 수 있는 벌레의 수를 구하기


해결 방안:

bfs 로 풀기 


해답 풀이전 참고 할점?

필자가 문제를 이해를 못한거 일 수 도있음 

먼저 가로세로가 10, 8 의 2차원 배열이면 

실제로는 아래와 같이 배열이 뽑히는데 이 케이스에서 입력값이 리스트의 범위 의 값을 넘어가는 값을 입력받는 경우가 있다.
그래서 그냥 반대로값을 넣어서 진행하였다(아마 필자가 빡대가리 인것 같다...)


이러한 경우 때문에 가로 세로 의 값을 반대로 받아서 했다
따라서 10,8 을 받으면 8x10 형태의 배열을 만들어서 풀이를 진행 하였다 



풀이는 다음과 같다.


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
from collections import deque
import sys
 
dx=[0,0,1,-1]
dy=[1,-1,0,0]
 
t= int(sys.stdin.readline())
 
def bfs(g,a,b):
    q=deque()
    q.append((a,b))
    g[a][b]=0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx= x+dx[i]
            ny= y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if g[nx][ny]==1:
                g[nx][ny]=0
                q.append((nx,ny))
    return
for i in range(t):
    #정답 변수
    cnt =0
    # 가로 세로 배추 위치의 개수
    n,m,k=map(int,sys.stdin.readline().split())
    # 밭 그래프
    g=[[0]*m for _ in range(n)]
    for j in range(k):
        x,y=map(int, sys.stdin.readline().split())
        g[x][y]=1
    for a in range(n):
        for b in range(m):
            if g[a][b]==1:
                bfs(g,a,b)
                cnt +=1
    print(cnt)
cs