백준 1012 : 유기농 배추 (파이썬)

BFS, DFS로 풀 수 있는 연결 요소의 개수 찾기 문제이다.

(DFS로 풀 때는 재귀함수로 푸는 경우가 많은데 재귀 깊이 제한으로 인한 에러를 조심할 것)

 

백준 1260 : DFS와 BFS (파이썬)

 

DFS, BFS 에 대한 기본 작동원리에 대해 자세하게 포스팅 한 적이 있으니 아래 코드가 이해되지 않는 경우 한 번 보고 오자.

---

DFS 코드 :

import sys
sys.setrecursionlimit(10 ** 6) # 재귀 깊이 제한 해제
def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= M:
        return False
    elif field[x][y]:
        field[x][y] = 0
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x + 1, y)
        dfs(x, y - 1)
        return True
    return False
T = int(sys.stdin.readline())
for _ in range(T):
    total = 0
    M, N, K = map(int, sys.stdin.readline().split())
    field = [[0] * M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        field[y][x] = 1
    for i in range(N):
        for j in range(M):
            if dfs(i, j):
                total += 1
    print(total)

---

BFS 코드 :

import sys
from collections import deque
queue = deque()
def bfs(x, y):
    first_x = x
    first_y = y
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    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 nx >= N or ny < 0 or ny >= M:
                continue
            if field[nx][ny] == 1:
                field[nx][ny] += field[x][y]
                queue.append((nx, ny))
    return field[x][y]
T = int(sys.stdin.readline())
for _ in range(T):
    res = []
    total = 0
    M, N, K = map(int, sys.stdin.readline().split())
    field = [[0] * M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        field[y][x] = 1
    for x in range(N):
        for y in range(M):
            if field[x][y] == 1:
                res.append(bfs(x, y))
    print(len(res))

 

first_x, first_y 를 해 준 이유는 자꾸 이미 방문한 맨 첫 번째 시작 노드도 탐색을 하면서 탐색길이 누적을 시켜주는 게 보기 싫어서 그랬다. 저거 없어도 정답은 나온다.

---

기본적인 문제라서 어렵지 않게 풀 수 있었다.