79. Python 백준 1012 번 유기농 배추 자세한 설명
안녕하세요 코딩하는 덕구입니다.
그래프 탐색 문제인 1012 번 유기농 배추 파이썬 자세한 설명입니다.
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
먼저 백준 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 번 이었습니다. 감사합니다.