[백준 1012번-유기농 배추]-파이썬

백준 1012번 파이썬풀이

<문제>

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

1012번: 유기농 배추

<풀이>-DFS알고리즘(재귀함수)사용!!!!

배추가 심어져있는곳은 1 심어져 있지 않은곳은 0이다.
그래프를 돌면서 배추가 심어져있는곳에서 DFS알고리즘을 적용한다.
해당위치에서 DFS알고리즘이 종료될때마다 count+=1을 해준다.

-DFS알고리즘 설명-

배추가 심어져 있는곳에서 상,하,좌,우 네가지 방향을 살핀다.

만약 네가지 방향중 배추가 심어져 있고 아직 방문하지 않은 경우(graph[x][y]=1,visitied[x][y]=False] 해당위치에서 dfs알고리즘을 호출한다.

※방문여부를 확인하는 두가지 방법※
1)밑의 코드 처럼 visited배열 사용
2)다음과 같이 dfs호출시 graph에서 해당 위치의 값을 -1로 변경

if graph[nx][ny]==1:
	graph[nx][ny] = -1
	dfs(nx,ny)

-주의점-

문제에서 배추가 심어져 있는곳의 위치를 입력받을때 열의 갯수와 y의 위치를 먼저 입력받게 되어있다.

따라서 그래프에 저장할경우 다음과 같이 저장해야한다.

m,n,k = map(int,input().split())
graph = [[0]*m for _ in range(n)]
for _ in range(k):
        a,b = map(int,input().split())
        graph[b][a] = 1

또한 재귀함수를 사용할때 다음과 같은 코드를 사용하지 않으면 런타임 에러가 발생할 수 있으니 참고하자.

import sys
sys.setrecursionlimit(10000)

<코드>-파이썬

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    visited[x][y] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=0 and ny>=0 and nx<n and ny<m:
            if not visited[nx][ny] and graph[nx][ny]==1:
                dfs(nx,ny)


T = int(input())
for _ in range(T):
    m,n,k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    count = 0
    for _ in range(k):
        a,b = map(int,input().split())
        graph[b][a] = 1
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(i,j)
                count+=1
                
    print(count)