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

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

1012번: 유기농 배추

import sys
sys.setrecursionlimit(10**6)

T = int(input())

def dfs(x,y):

    if x>=m or x<0 or y>=n or y<0 or graph[y][x]==0:
        return False
        
    graph[y][x] = 0
    visit[y][x] = 1

    dfs(x+1,y)
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x,y-1)


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

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



    for i in range(n):
        for j in range(m):

            if visit[i][j] == 0 and graph[i][j] == 1:
                dfs(j,i)
                cnt+=1
    print(cnt)

DFS로 푸니까 깊이에 대한 문제가 있다.. 이문제를 해결하기 위해서는 다른 방법을 써야한다. 

BFS로 푸는법도 숙지해야겠다.

import sys
from collections import deque
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    if graph[x][y] == 0 or visited[x][y]==1:
        return False
    q = deque()
    q.append((x,y))

    while q:
        cur_x, cur_y = q.popleft()

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 0 and visited[nx][ny] != 1:
                visited[nx][ny] = 1
                q.append((nx,ny))

    return True

t = int(input())

for _ in range(t):
    count = 0
    m,n,k = map(int, input().split())
    graph = [[0]*m for _ in range(n)]
    visited = [[0]*m for _ in range(n)]
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x] = 1
    for i in range(n):
        for j in range(m):
            if bfs(i,j):
                count +=1
    print(count)

너비 탐색으로도 풀어봤는데 이렇게 풀어도 되나?

약간 지저분하게 푼거 같기도...? 한디 어쨋든 답은 맞는다

 

from collections import deque

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

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

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

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

이건 다른분 풀이인데 그냥 배추 인거 확인하면 그래프 자체를 0으로 바꾼다 

나처럼 visited 만들필요가 없다...!

이런걸 까먹고 있었다니!