[백준] 1012 - 유기농 배추 (Python)

문제 설명

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

1012번: 유기농 배추

---

문제 풀이

이 문제는 BFS, DFS 두 방법 다 사용 가능하다

그래서 두 가지 방법으로 풀어보았다! 

 

1. DFS

배추가 심어진 땅의 개수를 구하는 것이기 때문에 가장 먼저 DFS로 푸는 방법을 떠올렸다

재귀를 돌면서 아직 방문하지 않았으면서 값이 1인 부분을 찾고, 재귀가 끝나면 return True를 해준다

반복문으로 dfs 함수를 호출해 true면 result를 증가해준다

import sys

sys.setrecursionlimit(10000)


def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    if not visited[x][y] and ground[x][y] == 1:
        visited[x][y] = True
        for p in range(4):
            nx = x + dx[p]
            ny = y + dy[p]
            dfs(nx, ny)
        return True
    return False


TC = int(input())

for t in range(TC):
    m, n, k = map(int, input().split())
    ground = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(k):
        a, b = map(int, input().split())
        ground[b][a] = 1

    result = 0

    for i in range(m):
        for j in range(n):
            if dfs(j, i):
                result += 1
    print(result)

 

 

 

2. BFS

BFS는 상하좌우를 확인하면서 아직 방문하지 않았고, 값이 1이면 큐에 넣어주고 

큐에서 pop해가면서 확인하면 된다

넘 쉬운 문제

from collections import deque


def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
    return True


T = int(input())

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

for t in range(T):
    m, n, k = list(map(int, input().split()))
    graph = [[0 for _ in range(m)] for __ in range(n)]
    visited = [[False] * m for _ in range(n)]
    point = []
    result = 0

    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1
        point.append((b, a))

    for p in point:
        a, b = p
        if not visited[a][b] and graph[a][b] == 1:
            bfs(a, b)
            result += 1

    print(result)

 

 

 

참고로 검색 대상이 엄청 크지 않으면 단순 속도는 BFS가 더 빠르다