[BOJ] #1012 - 유기농 배추

1012번: 유기농 배추

 

 

** 문제 유형

• DFS, BFS

 

** 풀이

1. 연결 요소의 개수를 세는 문제
2. 모든 정점에 대하여 DFS or BFS를 수행하고, 한번 방문한 정점은 다시 확인하지 않음
3. 전체적으로 DFS or BFS를 수행한 총 횟수를 계산
4. DFS or BFS 응용 문제 중에서 출제 비중이 매우 높은 유형 중 하나임
5. DFS로 문제를 푸는 경우, sys 라이브러리의 setrecursionlimit() 함수 설정 필요

 

 

# 방법 1
import sys
sys.setrecursionlimit(100000) # dfs 사용

def dfs(x, y):
    visited[x][y] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상, 하, 좌, 우 4곳만 확인

    for dx, dy in directions:
        nx, ny = x + dx, y + dy

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if array[nx][ny] and not visited[nx][ny]: # 배추가 심어져 있고, 아직 방문하지 않았으면
            dfs(nx, ny)

---

for _ in range(int(input())):
    m, n, k = map(int, input().split())

    array = [[0] * m for _ in range(n)] # 배추 
    visited = [[False] * m for _ in range(n)] # 방문 상태

    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1

    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]: # 배추가 심어져 있고, 아직 방문하지 않았으면
                dfs(i, j)
                result += 1

    print(result)

 

# 방법 2
import sys
sys.setrecursionlimit(100000)

def dfs(x, y):
    array[x][y] = 0

    for r, c in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if 0 <= r < n and 0 <= c < m:
            if array[r][c] == 1:
                dfs(r, c)

for _ in range(int(input())):
    m, n, k = map(int, input().split())

    array = [[0] * m for _ in range(n)]

    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1

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

    print(result)