[백준 파이썬] # 1012 유기농 배추 (DFS 풀이)

Silver II

# 1012 유기농 배추

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

1012번: 유기농 배추

 

풀이 (DFS)

# 재귀 limit 설정
import sys
sys.setrecursionlimit(10000)

### 2
# dfs 정의
def dfs(x, y):
    # 상하좌우 확인을 위해 dx, dy 생성
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    # 네 방향 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < M) and (0 <= ny < N):  # nx:ny ↔ M:N 범위 참고
            if graph[ny][nx] == 1:
                graph[ny][nx] = -1  # 배추가 인접할 때 체커
                dfs(nx, ny)

### 1                    
T = int(input())

for i in range(T):
    M, N, K = map(int, input().split())  # M:가로, N:세로, K:개수
    graph = [[0]*M for i in range(N)]
    cnt = 0

    # 배추 위치에 1 표시
    for j in range(K):
        X, Y = map(int, input().split())
        graph[Y][X] = 1

### 3        
    # dfs 활용해서 배추 그룹 수 세기
    for x in range(M):
        for y in range(N):
            if graph[y][x] == 1:
                dfs(x, y)
                cnt += 1

    # 정답을 위한 출력
    print(cnt)

 

• sys.setrecursionlimit(10000) 를 입력하지 않으면 런타임 오류가 발생한다.
• 파이썬의 기본 재귀 한도는 1000이고, 재귀 깊이가 1000을 넘어갈 경우 모듈을 추가해야 한다
• BFS로 풀면 런타임 오류가 발생하지 않는다고 한다
• graph의 index를 사용할 때 행과 열을 바꿔줘야 한다는 걸 잊지 말자
• graph[ny][nx]를 확인하고 -1로 변경해서 체커 역할을 한다
• x, y 위치를 지정할 때 헷갈리지 않도록 주의하도록 하자

연습을 반복하더니 답을 외워버린게 아닌가.. 싶다(흠..)

BFS 풀이도 연습해둬야 하겠다