[백준 / 1012] 유기농 배추 - Python

입력받은 모든 그래프를 돌면서 1이 있는 처음 좌표를 중심으로 모든 인접한 1을 2로 만드는 함수를 호출한다. 이러한 과정을 반복하며 함수가 몇 번 호출됐는지를 count 해서 출력한다.

<입력>

for _ in range(int(input())):
    M, N, K = map(int, input().split())
    
    graph = [[0 for _ in range(M)] for _ in range(N)]

    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1

 

테스트 케이스를 입력 받아 그 수만큼 for문을 돌린다.

가로길이 M, 세로 길이 N, 배추의 위치 K를 입력받는다.

 

밭의 그래프인 N * M 크기를 그려준다.

K 수만큼 입력을 받아서 해당 좌표를 1로 바꿔준다.

    count = 0

<수행>

    count = 0
    
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                count += 1
                search(graph, j, i, M, N)

 

함수 호출 수인 count를 세기 위해 count를 선언해준다.

 

그래프의 모든 위치를 탐색하면서 1인 좌표를 함수에 전달한다. 함수를 호출하면서 count를 1 증가시킨다. 

<함수>

def search(graph, x, y, M, N):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    queue = [[x, y]]

    while queue:
        current_x, current_y = queue.pop()

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

            if 0 <= new_x < M and 0 <= new_y < N and graph[new_y][new_x] == 1:
                graph[new_y][new_x] = 2
                queue.append([new_x, new_y])

 

dx, dy는 인접 좌표를 확인하기 위해 상, 하, 좌, 우로 움직이기 위한 변수이다.

queue에 x, y 좌표를 넣고 queue가 빌 때까지 while문을 반복한다.

 

현재 x와 y를 queue에서 빼온다.

현재 좌표를 기준으로 상, 하, 좌, 우로 움직여 새 좌표를 설정한다. 새 좌표가 graph의 범위 안에 있고, 값이 1이라면 해당 값을 2로 바꿔주고, 해당 좌표를 queue에 넣어준다.

 

따로 반환 값은 없어도 되고 graph만 접근한 1의 값을 2로 바꿔주면 된다.

<출력>

   print(count)

 

함수를 호출한 수는 곧 배추 흰 지렁이의 수이므로 count를 출력한다.

 

<전체 코드>

def search(graph, x, y, M, N):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    queue = [[x, y]]

    while queue:
        current_x, current_y = queue.pop()

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

            if 0 <= new_x < M and 0 <= new_y < N and graph[new_y][new_x] == 1:
                graph[new_y][new_x] = 2
                queue.append([new_x, new_y])


for _ in range(int(input())):
    M, N, K = map(int, input().split())
    
    graph = [[0 for _ in range(M)] for _ in range(N)]

    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1

    count = 0

    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                count += 1
                search(graph, j, i, M, N)

    print(count)