백준 1012 유기농 배추 Python 3

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

1012번: 유기농 배추

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1012.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def dfs(x, y):
    for ddx, ddy in zip(dx, dy):
        nx, ny = x+ddx, y+ddy
        if 0 <= nx < M and 0 <= ny < N and not visit[ny][nx] and area[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

T = int(input())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for _ in range(T):
    M, N, K = map(int, input().split())
    area = [[0]*M for _ in range(N)]
    worms = 0
    for _ in range(K):
        x, y = map(int, input().split())
        area[y][x] = 1
    visit = [[0] * M for _ in range(N)]
    for y in range(N):
        for x in range(M):
            if area[y][x] and not visit[y][x]:
                visit[y][x] = 1
                dfs(x, y)
                worms += 1
    print(worms)

---

풀이 과정

풀이 시간 8분

import sys
#최대 50x50 그래프를 탐색해야하므로 재귀 제한을 늘린다
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def dfs(x, y):
	#인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx, ny = x+ddx, y+ddy
        #범위 안에 있으면서 이전에 방문하지 않았고, 배추가 있는 칸이라면 탐색을 이어나간다
        if 0 <= nx < M and 0 <= ny < N and not visit[ny][nx] and area[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

T = int(input())

#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for _ in range(T):
	#초기화
    M, N, K = map(int, input().split())
    area = [[0]*M for _ in range(N)]
    worms = 0
    for _ in range(K):
        x, y = map(int, input().split())
        #배추가 있는 칸 1로 설정
        area[y][x] = 1
        
    visit = [[0] * M for _ in range(N)]
    for y in range(N):
        for x in range(M):
        	#배추가 있는 칸이면서 이전에 방문하지 않았다면, 새 영역을 탐색한다
            if area[y][x] and not visit[y][x]:
                visit[y][x] = 1
                dfs(x, y)
                #지렁이 한 마리 추가
                worms += 1
                
    print(worms)
    
#시간복잡도 = O(V+E), 공간복잡도 = O(n)