1012번 유기농 배추

문제 설명

1012번: 유기농 배추

 

나의 풀이

from collections import deque


def bfs(graph, start_node):
    if not graph[start_node[0]][start_node[1]]:
        return False

    q = deque()
    q.append(start_node)
    graph[start_node[0]][start_node[1]] = 0

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while q:
        current_y, current_x = q.popleft()

        for i in range(4):
            nx = current_x + dx[i]
            ny = current_y + dy[i]

            if 0 <= ny < len(graph) and 0 <= nx < len(graph[0]) and graph[ny][nx]:
                graph[ny][nx] = 0
                q.append((ny,nx))
                
    return True


t = int(input())
for _ in range(t):
    m, n, cabbage_num = map(int, input().split())

    xy_points_list = []
    for _ in range(cabbage_num):
        x, y = map(int, input().split())
        xy_points_list.append((x,y))


    graph = [[0]*n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if (i,j) in xy_points_list:
                graph[i][j] = 1

    cnt = 0
    for i in range(len(graph)):
        for j in range(len(graph[0])):
            result = bfs(graph, (i,j))
            if result:
                cnt += 1

    print(cnt)

 섬의 갯수를 구하는 문제와 같다. 테스트 케이스 갯수가 주어지고 행렬과 배추의 갯수에 따라 각 구간의 갯수를 구하면 되는 문제이다.

주어지는 입력값이 배추의 위치 x,y점으로 하나 씩 주어진다. 위치에 대한 정보 리스트에 따로 저장해두고, 행렬 그래프에 각 위치에 1로 주어진 그래프로 만들어 준다.

만들어둔 bfs함수는 모든 점들을 돌아보면서 방문한 위치는 0으로 바꿔주며 그래프를 업데이트 시켜준다. 해당 그래프에 0인값에는 false로 각 구간이 0으로 바뀌는 곳에 방문할 때는 카운트가 올라간다.