[백준] 1012번(python 파이썬)

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

 

---

배추흰 지렁이가 인접한(상, 하, 좌, 우) 배추를 보호 한다고 한다. 즉, 이 문제는 배추의 영역을 구하는 문제이다. 

DFS, BFS둘다 사용 할 수 있지만 DFS의 경우 재귀의 횟수에 따라 메모리, 시간초과가 뜰 수 있다.

이때 sys.setrecursionlimit(n) 을 사용하여 제귀횟수를 제한할 수 있지만 BFS를 사용하는 것이 좋아보인다.

 

여기서 노드는 배열의 좌표라고 생각한다.

DFS

시작 노드에서 인접한 노드 선택하여 방문처리를 하고 탐색을 들어간다.

더이상 탐색할 노드가 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다.

 

BFS

BFS는 큐를 이용하여 문제를 풀 수 있다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

---

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)

test_count = int(input())

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


def Bfs(cur_x, cur_y, graph, visited):
    visited[cur_x][cur_y] = True
    queue = deque()
    queue.append((cur_x, cur_y))

    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            next_x = pop_x + dx[i]
            next_y = pop_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue
            if not visited[next_x][next_y] and graph[next_x][next_y] == 1:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = True


def Dfs(cur_x, cur_y, graph, visited):
    visited[cur_x][cur_y] = True

    for i in range(4):
        next_x = cur_x + dx[i]
        next_y = cur_y + dy[i]

        if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
            continue
        if not visited[next_x][next_y] and graph[next_x][next_y] == 1:
            Dfs(next_x, next_y, graph, visited)



for i in range(test_count):
    row, col, k = map(int, input().split())
    graph = [[0]*col for _ in range(row)]
    visited = [[False]*col for _ in range(row)]

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

    result = 0
    for i in range(row):
        for j in range(col):
            if not visited[i][j] and graph[i][j] == 1:
                Bfs(i, j, graph, visited)
                #Dfs(i, j, graph, visited)
                result += 1

    print(result)