[Python][백준_1012] 유기농 배추 (BFS)

문제

1012번: 유기농 배추

풀이과정

아래의 예시로 설명을 해보겠습니다.

1
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6

 

위의 경우를 arr 에 저장해보면 아래와 같은 결과가 나옵니다. (0은 생략)

 

한마리의 지렁이가 서로 붙어있는 배추들을 보호할 수 있기 때문에 아래와 같이 5마리의 지렁이로 모든 배추를 보호 할 수 있습니다.

아래의 코드로 보호되지 못한 배추의 위치를 찾고 

def getPosition(N, M, arr):
    for i in range(M):
        for j in range(N):
            if arr[i][j] == 1:
                return [i, j]
    return [-1, -1]

 

BFS 를 이용하여 서로 붙어있는 배추들을 찾은 뒤, 0으로 바꿔 보호될 수 있음을 표시합니다.

def giveWorm(N, M, arr):
    printAll(N, M, arr)
    [x, y] = getPosition(N, M, arr)
    print(x, y)
    arr[x][y] = 0
    near = [[x, y]]
    while(len(near) > 0):
        printAll(N, M, arr)
        print(near)
        x, y = near[0][0], near[0][1]
        near.pop(0)
        for d in Dir:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < M and 0 <= ny < N and arr[nx][ny] == 1:
                near.append([nx, ny])
                arr[nx][ny] = 0

 

위의 과정을 보호되지 못한 배추가 없을때까지 지렁이를 늘려가면서 반복하면 원하는 결과를 얻을 수 있습니다.

while(getPosition(N, M, arr)[0] != -1):
            arr = giveWorm(N, M, arr)
            answer += 1

이를 코드로 나타내면 아래와 같습니다.

 

Code

Dir = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        
def getPosition(N, M, arr):
    for i in range(M):
        for j in range(N):
            if arr[i][j] == 1:
                return [i, j]
    return [-1, -1]

def giveWorm(N, M, arr):
    [x, y] = getPosition(N, M, arr)
    arr[x][y] = 0
    near = [[x, y]]
    while(len(near) > 0):
        x, y = near[0][0], near[0][1]
        near.pop(0)
        for d in Dir:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < M and 0 <= ny < N and arr[nx][ny] == 1:
                near.append([nx, ny])
                arr[nx][ny] = 0
            
    return arr
    
if __name__ == "__main__":
    T = int(input())
    
    for _ in range(T):
        answer = 0
        M, N, K = map(int, input().split())
        arr = [[0 for _ in range(N)] for _ in range(M)]
        for _ in range(K):
            x, y = map(int, input().split())
            arr[x][y] = 1
            
        while(getPosition(N, M, arr)[0] != -1):
            arr = giveWorm(N, M, arr)
            answer += 1
        print(answer)