그래프 + 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
'프로그래밍 > 코딩테스트' 카테고리의 다른 글
[프로그래머스] MYSQL 코드 정리 (0) | 2022.07.22 |
---|---|
[BOJ] 숨바꼭질 (0) | 2022.07.21 |
[BOJ] 연결 요수의 개수 파이썬 시간초과 (0) | 2022.07.21 |
[BOJ] 1920 수 찾기(이분탐색) (0) | 2022.07.19 |
[프로그래머스] SQL lv2 ) 중성화 여부 파악하기 MySQL (0) | 2022.07.18 |