2022.02.13 [백준] (python 파이썬) 유기농 배추

 

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

1012번: 유기농 배추

---

풀이

아래 코드는 bfs를 이용하여 해결했다.

입력받은 크기 만큼 arr2차원배열을 생성했고 배추가 있는 좌표에 1을 넣어주었다.

그리고 나중에 2중 for문을 돌리지 않기 위해 배추의 좌표를 미리 cab배열에 담아 주었다.

각 좌표를 모두 입력 받은 후 for문을 돌려 cab의 담긴 좌표의 arr값이 1이면 bfs함수를 호출했다.

bfs함수가 끝나면 배추가 모여있는 집단의 arr값을 모두 0으로 바꿨으므로 cnt를 증가시켰다.

import sys
from collections import deque
 
input=sys.stdin.readline
 
dx=[1,-1,0,0]
dy=[0,0,1,-1]
 
def bfs(x,y):
    deq=deque()
    deq.append([x,y])
    arr[x][y]=0
    while deq:
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if arr[nx][ny]==1:
                    deq.append([nx,ny])
                    arr[nx][ny]=0
 
 
for _ in range(int(input())):
    cab=[]
    m,n,k=map(int, input().split())
    arr=[[0]*m for _ in range(n)]
 
    for _ in range(k):
        x,y=map(int, input().split())
        arr[y][x]=1
        cab.append([y,x])
    cnt=0
    for i in cab:
        if arr[i[0]][i[1]]==1:
            bfs(i[0],i[1])
            cnt+=1
    print(cnt)

 

아래 코드는 dfs를 이용하여 작성했다.

dfs는 재귀를 이용하기 때문에 재귀 깊이 제한을 sys.setrecursionlimit(10**6)을 이용하여 10^6만큼 늘려주었다.

다른 코드는 bfs와 동일하지만 dfs함수에서 재귀를 사용하였다.

import sys
sys.setrecursionlimit(10**6)
 
input=sys.stdin.readline
 
dx=[1,-1,0,0]
dy=[0,0,1,-1]
 
def dfs(x,y):
    arr[x][y]=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if arr[nx][ny]==1:
                dfs(nx,ny)
 
for _ in range(int(input())):
    cab = []
    m,n,k=map(int, input().split())
    arr=[[0]*m for _ in range(n)]
 
    for _ in range(k):
        x,y=map(int, input().split())
        arr[y][x]=1
        cab.append([y,x])
    cnt=0
    for i in cab:
        if arr[i[0]][i[1]]==1:
            dfs(i[0],i[1])
            cnt+=1
    print(cnt)