[python] 백준 1012번 "유기농배추"(DFS/BFS)

문제 풀이 (BFS)

• 입력을 받은 후 그래프가 입력되는 횟수만큼 탐색 수행
• 그래프의 값이 1인경우(배추가 있는 경우) bfs 탐색 진행
• 탐색을 진행할 때 마다 같은 좌표의 탐색이 반복되지 않도록 그래프의 값을 0으로 초기화
• bfs 연산이 한 번 끝날 때 마다 연결되어 있는 곳의 탐색을 마친 것 이므로  카운트 
• 카운트 한 횟수 출력

코드

from collections import deque
num = int(input())

for i in range(num):
    rr, cc, num = map(int,input().split())
    graph = [[0] * rr for _ in range(cc)]
    for i in range(num):
        x, y = map(int,input().split())
        graph[y][x] = 1

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

    def bfs(a,b):
        queue = deque()
        queue.append((a, b))
        graph[a][b] = 0
        while queue:
            r,c = queue.popleft()
            for i in range(4):
                new_r = r + dy[i]
                new_c = c + dx[i]
                if 0 <= new_r < cc and 0 <= new_c < rr and graph[new_r][new_c] == 1:
                    queue.append((new_r, new_c))
                    graph[new_r][new_c] = 0

        return

    result = 0
    for i in range(cc):
        for j in range(rr):
            if graph[i][j] == 1:
               bfs(i, j)
               result += 1
    print(result)

문제 풀이 (DFS)

• 입력을 받은 후 그래프가 입력되는 횟수만큼 탐색 수행
• 그래프의 값이 1인경우 중복연산이 수행되지 않도록 그래프의 값을 0으로 변경
• 그 후 상하좌우를 탐색하여 새로운 좌표 값을 DFS에 넘기기
• DFS가 수행 되면 조건에 맞는지 확인(좌표가 범위를 벗어나지 않는지, 그래프의 값이 1인지)
• 조건에 맞다면 다시 새로운 좌표 탐색하여 새 좌표 값을 재귀적으로 넘겨주기
• 위 과정을 계속해서 반복 
• DFS의 결과가 참인 경우 덩어리에 대한 연산을 마친 것 이므로 카운트 
• 카운트 값 출력

코드

import sys
sys.setrecursionlimit(10 ** 6)
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
t = int(input())
result = 0

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

    def dfs(y,x):
        # dfs 수행 조건
        if 0 <= y < n and 0 <= x < m and graph[y][x] == 1:
            graph[y][x] = 0

            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                dfs(ny,nx)

            return True
        return False

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

  -> 이 문제는 DFS 연산을 수행 했을 때 시간과 메모리가 더 효율적이었다

비슷한 문제

2667번: 단지번호붙이기