79. Python 백준 1012 번 유기농 배추 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 1012 번 유기농 배추 파이썬 자세한 설명입니다.

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

먼저 백준 1012 번 파이썬 정답 코드입니다.

 

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

def BFS(i, j):
    d = deque()
    d.append((i, j))
    while d:
        loc = d.popleft()
        for n in range(4):
            x = x_dir[n] + loc[0]
            y = y_dir[n] + loc[1]
            if 0 <= x < M and 0 <= y < N:
                if graph[x][y] == 1:
                    graph[x][y] = 0
                    d.append((x, y))

def DFS(i, j):
    graph[i][j] = 0
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x and x < M and 0 <= y and y < N:
            if graph[x][y] == 1:
                DFS(x, y)

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0 for _ in range(N)]for _ in range(M)]
    for _ in range(K):
        i, j = map(int, input().split())
        graph[i][j] = 1
    num = 0
    for m in range(M):
        for n in range(N):
            if graph[m][n] == 1:
                BFS(m, n) #or DFS(m, n) 
                num += 1
    print(num)

 

DFS, BFS 두 방식으로 모두 구현해봤습니다.

BFS, DFS 둘 중 아무거나 사용하셔도 상관 없습니다.

배추근처에 지렁이가 한마리라도 있다면 인접한 배추를 이동하면서 연결된 배추들을 모두 지킬 수 있기 때문에 

배추 밭 전체를 탐색하면서 방문하지 않은 배추가 있으면 방문하여 지렁이 한마리를 배정해주고

DFS 혹은 BFS를 사용하여 연결된 모든 배추를 방문처리를 해주면

연결되지 않은 배추들 마다 지렁이 한 마리씩 배정이 됩니다.

 

위의 직관을 가지고 코드를 구현해 봅시다. 

 

Test Case 만큼 반복하고, 그래프, M, N, K 를 입력받습니다.

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

 

그래프를 탐색하면서, 방문하지 않은 배추가 있다면 BFS 혹은 DFS를 진행해주고, 

배추 지렁이 한 마리씩 배정해줍니다.

for m in range(M):
    for n in range(N):
        if graph[m][n] == 1:
            BFS(m, n) #or DFS(m, n)
            num += 1

 

그래프 방문이 끝나고 나면 지렁이 마리수를 출력해주면 됩니다.

print(num)

 

 

DFS 와 BFS는 다음과 같이 구현했습니다.

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

def BFS(i, j):
    d = deque()
    d.append((i, j))
    while d:
        loc = d.popleft()
        for n in range(4):
            x = x_dir[n] + loc[0]
            y = y_dir[n] + loc[1]
            if 0 <= x < M and 0 <= y < N:
                if graph[x][y] == 1:
                    graph[x][y] = 0
                    d.append((x, y))

def DFS(i, j):
    graph[i][j] = 0
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x and x < M and 0 <= y and y < N:
            if graph[x][y] == 1:
                DFS(x, y)

 

여기서 DFS와 BFS를 진행하면서 방문한 노드는 기존 1에서 0 으로 변경하여

다음번에 다시 방문하지 않도록 처리하였습니다. 

 

Python 백준 1012 번 최종 코드입니다.

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

def BFS(i, j):
    d = deque()
    d.append((i, j))
    while d:
        loc = d.popleft()
        for n in range(4):
            x = x_dir[n] + loc[0]
            y = y_dir[n] + loc[1]
            if 0 <= x < M and 0 <= y < N:
                if graph[x][y] == 1:
                    graph[x][y] = 0
                    d.append((x, y))

def DFS(i, j):
    graph[i][j] = 0
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x and x < M and 0 <= y and y < N:
            if graph[x][y] == 1:
                DFS(x, y)

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0 for _ in range(N)]for _ in range(M)]
    for _ in range(K):
        i, j = map(int, input().split())
        graph[i][j] = 1
    num = 0
    for m in range(M):
        for n in range(N):
            if graph[m][n] == 1:
                BFS(m, n) #or DFS(m, n)
                num += 1
    print(num)

 

Python 백준 1012 번 이었습니다. 감사합니다.