1012. 유기농 배추

문제

코드

def bfs(x, y):
    q = deque()
    q.append((x,y))
    arr[y][x] = 0
    while q:
        j, i = q.popleft()
        for k in range(4):
            nj = j+dir[k][1]
            ni = i+dir[k][0]
            if 0<=ni<N and 0<=nj<M:
                if arr[ni][nj] == 1:
                    arr[ni][nj] = 0
                    q.append((nj,ni))

for tc in range(1, int(input())+1):
    M, N, K = map(int, input().split())
    arr = [[0]*M for _ in range(N)]
    dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for _ in range(K):
        x, y = map(int,input().split())
        arr[y][x] = 1

    cnt = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                """
                한번 bfs를 돌면 인접한 영역의 1을
                모두 0으로 만들어 cnt 수만 세면
                영역의 개수가 나온다
                """
                bfs(j, i)
                cnt += 1
    print(cnt)

풀이

백준 2667번 단지번호 붙이기와 유사한 문제고 더 쉬운버전
여기서 망설였던건 문제 내에서는 input이 array로 주어지지 않고 배추가 있는 위치만 주어져서 이거를 2차원 배열로 만들어야 할지 말지를 고민했었다. 인풋을 받는데 for, 이걸 arr로 만드는 for, 만든 arr를 돌아서 1을 찾는 for 로 총 3가지 for를 만들었어야 했기 때문인데 대충 검색으로 둘러보니 이게 맞나부다...

탐색 시작할 시작점은 그래프를 탐색하다가 1을 발견한 순간 bfs시작, 한번 bfs가 돌고 나면 인접한 곳에 있는 1을 모두 0으로 바꿔버리기 때문에 bfs가 도는 횟수가 영역의 개수라고 할 수 있다.