[BOJ 1012]유기농 배추(Python)

문제링크

유기농 배추

풀이 전 계획 및 생각

이전에 풀었던 단지번호 붙이기 문제와 동일한 문제였다. visited 배열을 이용해서 방문한 적 없는 노드들에대해서 dfs를 실행하고, 그 과정에서 방문한 노드들은 이미 다녀간 노드가 되기때문에, 그 노드에서는 탐색을 시작할 필요가 없다.
그래서 이 문제에서는 dfs를 시행한 횟수만 확인해주면 된다.
다양한 방법으로 dfs, bfs를 구현해보고싶었기 때문에, 이번 문제에서는 dfs를 스택을 이용해서 구현했다.

풀이

import sys

def dfs(x,y):
    visited[x][y] = True
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    stack = [[x,y]]
    while stack:
        cx,cy = stack.pop()
        visited[cx][cy] = True
        for dx, dy in directions:
            nx, ny = cx+dx, cy+dy
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if array[nx][ny] and not visited[nx][ny]:
                stack.append([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, sys.stdin.readline().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)

풀이하면서 막혔던 점과 고민했던 점

딱히 없었다.

풀이 후 알게된 개념과 소감

DFS, BFS를 제대로 구현할 줄만 알아도 비슷한 방식으로 풀 수 있는 문제가 많다는 것을 알았다.