[Python] 백준 1012번 : 유기농 배추

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

 

---

 

 

🚩DFS 코드

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

def dfs(x, y) :
    if x < 0 or y < 0 or x >= M or y >= N :
        return False
    
    if graph[y][x] == 1 :
        graph[y][x] = 0
    
        for i in range(4):
            dfs(x + dx[i], y + dy[i])
        
        return True
    
    return False

T = int(input())

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

for _ in range(T) :
    M, N, K = map(int, input().split())
    graph = [[0]*M for _ in range(N)]
    
    for _ in range(K) :
        x, y = map(int, input().split())
        graph[y][x] = 1
    
    cnt = 0
    for i in range(N) :
        for j in range(M) :
            if dfs(j, i) == True :
                cnt += 1
    
    print(cnt)

 

• 보통 파이썬의 재귀 최대 깊이가 1000으로 설정되어 있다고 한다.
  sys.setrecursionlimit()을 사용해서 재귀 최대 한도를 바꿔줘야 런타임 에러가 안난다.
• input = sys.stdin.readline 으로 지정하는게 보통인데 평소에 개행문자가 포함되는게 껄끄러워서 .rstrip()을 붙이는 습관이 있다. input = input = sys.stdin.readline().rstrip 으로 처음에 코드를 짰다가 런타임 에러(ValueError)가 발생해서 고생했다. 저렇게 input에 대입해버리면 rstrip 함수 객체 자체가 들어간다고 한다. 혹은 앞에 있는 readline() 함수가 실행되어서 에러가 뜰 수도 있다. 어쨌든 평범하게 input = sys.stdin.readline로 하자.

 

🚩DFS 코드

import sys
from collections import deque

def bfs(x, y) :
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            
            if graph[ny][nx] == 0:
                continue
            
            if graph[ny][nx] == 1:
                queue.append((nx,ny))
                graph[ny][nx] = 0
    
T = int(sys.stdin.readline())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
    
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().rstrip().split())
    graph = [[0]*M for _ in range(N)]
    
    for i in range(K):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        graph[y][x] = 1
    
    cnt = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                graph[i][j] = 0
                bfs(j, i)
                cnt += 1
                
    print(cnt)

 

 

 

이 문제에서 실수하기 쉬운 부분은 x와 y의 범위에 따른 범위 설정이다.

M은 가로길이, N은 세로 길이다.

좌표에서는 (M, N) 이지만 행렬, 리스트에서는 [N][M] 으로 입력해야 하므로 여기서 많이 런타임 에러를 일으키는 것 같다.

런타임 에러(IndexError)가 발생한다면 N, M을 잘 설정했는지 확인할 것