[백준] Python 1012번 유기농 배추 실버2 - 그래프

문제 : https://www.acmicpc.net/problem/1012
분류 : 그래프, 깊이, 너비 우선 탐색(DFS, BFS)

접근

1. 지렁이가 땅따먹을 수 있는 땅의 개수를 구하면 된다.
2. 1이 있는 곳에 동서남북으로 이동해보고 그 구역을 처리해준다.
   

슈도코드

if graph 1:
	BFS()

BFS():
	q에 들어온 값 삽입(위치)
    
    while queue:
    	현재 위치 = 큐에서 pop
        현재 위치 방문처리
        
        for 동서남북:
        	0 < 다음 위치 < 밭:
            	다음 위치가 0이 아니고 방문한적 없으면:
                	다음 위치 방문처리하고
                    값은 0으로 바꿔주고
                    q에 삽입
 
BFS()가 끝나면 cnt++하여 총 땅따먹기 한 땅의 개수 출력

풀이

from collections import deque

def solution():
    answer = []
    T = int(input()) # 테스트 케이스

    for i in range(T):
        y, x, cabbages = map(int, input().split()) # 세로, 가로, 배추의 갯수
        graph = [[0]*x for _ in range(y)]  # 그래프 배열

        for i in range(cabbages):
            y_index, x_index = map(int, input().split())
            graph[y_index][x_index] = 1

        visited = [[False]*x for _ in range(y)]
        cnt_earthworm = 0

        for i in range(y):
            for j in range(x):
                if graph[i][j] == 1:
                    BFS(y, x, graph, i, j, visited)
                    cnt_earthworm += 1

        print(cnt_earthworm)

def BFS(y, x, graph, i, j, visited):
    # 큐 생성
    queue = deque()
    # 동 서 남 북
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    # 시작 노드 큐에 삽입
    queue.append((i, j))
    # 큐가 빌 떄 까지
    while queue:
        # 현재 y, x 큐에서 꺼냄
        cur_y, cur_x = queue.popleft()
        # 방문 처리
        visited[i][j] = True

        for k in range(4):
            # 동 서 남 북 으로 이동
            next_y = cur_y + dy[k]
            next_x = cur_x + dx[k]

            # 밖으로 나가지 않고 N,M보다 크지 않을 때
            if next_y >= 0 and next_x >= 0 and next_y < y and next_x < x:
                # 해당 값이 0이 아니고 방문하지 않았을 때
                if graph[next_y][next_x] != 0 and visited[next_y][next_x] == 0:
                    # 방문 처리
                    visited[next_y][next_x] = True
                    # 인접한 노드는 가중치 증가
                    graph[next_y][next_x] = 0
                    queue.append((next_y, next_x))

solution()