[알고리즘] 백준 1012 유기농 배추 - 파이썬

기말고사 시즌이지만 시험공부가 너무 하기싫어서 한문제 더풀었다.. 처음에는 쉽게 풀리는 듯 했으나 이상하게 입력으로 가로, 세로 바꿔놓으면 헷갈린다.. 문제에서 가로를 m, 세로를 n으로 입력 받게 되어 있다. 난 아무생각없이 가로를 n 세로를 m으로 입력받고 혼자 중간에 패닉에 빠졌다.. 

 

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

1012번: 유기농 배추

 

풀이코드

1. DFS풀이

from sys import stdin
import sys
sys.setrecursionlimit(10**9)

t = int(input()) # 테스트케이스 2개
result_list = []

def make_graph(m, n, k):
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, stdin.readline().split())
        graph[y][x] = 1
    return graph


def dfs(y, x):
    if x <= -1 or x >= m or y <= -1 or y >= n:
        return False

    if graph[y][x] == 1:
        graph[y][x] = 0
        dfs(y-1, x)
        dfs(y+1, x)
        dfs(y, x-1)
        dfs(y, x+1)
        return True
    return False


for _ in range(t):
    result = 0
    m, n, k = map(int, stdin.readline().split())
    graph = make_graph(m, n, k)
    for i in range(n):
        for j in range(m):
            if dfs(i,j) == True:
                result += 1
    result_list.append(result)

print(*result_list, sep='\n')

풀이코드를 dfs버전과 bfs버전을 둘 다 돌려봤다. 지문을 보자마자 dfs로 풀면 쉽게 풀리겠다 생각했지만 런타임 에러 (RecursionError) 가 나왔다. 찝찝하기도 해서 bfs로 다시 풀었고 중간에 막혀서 다른 블로그를 참조했다.

 

2. BFS풀이 

# bfs풀이
from collections import deque
from sys import stdin

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


t = int(input()) # 테스트케이스 2개
result_list = []

def make_graph(m, n, k):
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, stdin.readline().split())
        graph[y][x] = 1
    return graph

def bfs(y, x):

    queue = deque([])
    queue.append([y, x])

    while queue:
        y, x = queue.pop()
        for d in range(4):
            xx = dx[d] + x
            yy = dy[d] + y
            if 0 <= xx < m and 0 <= yy < n:
                if graph[yy][xx] == 1:
                    graph[yy][xx] = 0
                    queue.append([yy, xx])


for _ in range(t):
    result = 0
    m, n, k = map(int, stdin.readline().split()) # m:가로, n:세로
    graph = make_graph(m, n, k)
    for i in range(n): # 세로
        for j in range(m): # 가로
            if graph[i][j] == 1:
                bfs(i, j)
                result += 1
    result_list.append(result)

print(*result_list, sep='\n')