그래프 + DFS/BFS 문제 이다

 

큰 구조는 다음과 같다

2차원 행렬에서 양배추가 심어져있는 좌표들을 처음부터 끝까지 훑고

양배추가 심어져있다면 그 양배추 상하좌우 연결된 다른 양배추를 찾기 위한 DFS 혹은 BFS를 돌리는 것이다.

 

 

#DFS 버전 - 재귀

기본 사항

1) matrix 2차원 행렬 : 배추가 심어져 있는 곳은 1, 없는 곳은 기본값 0, 들렸던 곳은 -1

matrix = [[0]*열 for _ in range(행)]

2) dfs 내에서 상하좌우를 탐색할 수 있도록 하는 1차원 배열

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

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

 

import sys
sys.setrecursionlimit(10000)



def dfs(x,y):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0<=nx<N) and (0<=ny<M):
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = -1
                dfs(nx,ny)



T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())
    matrix = [[0]*M for _ in range(N)]
    cnt = 0
    
    #matrix에 양배추 위치 표시
    for _ in range(K):
        m, n = map(int, input().split())
        matrix[n][m] = 1
    
    #matrix 전체 탐색
    for i in range(N):#행
        for j in range(M):
            if matrix[i][j] == 1:
                dfs(i,j)
                cnt+=1
    print(cnt)

https://fullmoon1344.tistory.com/85

 

[백준 1012] 유기농 배추 - Python (그래프, DFS)

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한

fullmoon1344.tistory.com

#BFS - deque 이용

from collections import deque

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

def bfs(x,y):
    
    que = deque()
    que.append((x,y))
    matrix[x][y] = 0
    while que:
        a, b = que.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if (0<=nx<N) and (0<=ny<M):
                if matrix[nx][ny] == 1:
                    matrix[nx][ny] = -1
                    que.append((nx,ny))



T = int(input())

for _ in range(T):
    #M 가로 길이 : 열, N: 세로 길이 : 행
    M, N, K = map(int, input().split())
    matrix = [[0]*M for _ in range(N)]
    cnt = 0
    
    #matrix에 양배추 위치 표시
    for _ in range(K):
        n, m = map(int, input().split())
        matrix[m][n] = 1
    
    #matrix 전체 탐색
    for i in range(N):#행
        for j in range(M):#열
            if matrix[i][j] == 1:
                bfs(i,j)
                cnt+=1
    print(cnt)

https://hongcoding.tistory.com/72

 

[백준] 1012 유기농 배추 (Python 파이썬)

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것

hongcoding.tistory.com

 

+ Recent posts