[문제 풀이] 백준 1012

1012번: 유기농 배추

해결 과정

cabbages를 하나씩 pop 하면서 BFS를 돌렸다. 

나의 풀이

from collections import deque

T = int(input())

for i in range(T):
    M, N, K = map(int, input().split())

    cabbages = []
    for i in range(K):
        a, b = map(int, input().split())
        cabbages.append((a, b))

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

    queue = deque()
    count = 0

    while cabbages:
        queue.append(cabbages.pop())
        while queue:
            cur = queue.popleft()
            for i in range(4):
                x = cur[0] + dx[i]
                y = cur[1] + dy[i]
                if (x, y) in cabbages:
                    queue.append((x, y))
                    cabbages.remove((x, y)) 
        count += 1

    print(count)

 

다른 풀이

이중 for 문으로 (x, y)를 모두 돌면서 DFS/BFS를 사용하는 풀이들. 방문 여부는 1 -> 0 으로 바꿔주면서 풀이.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
T = int(input())

def search(x,y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return

    if graph[x][y] == 0:
        return


    graph[x][y] = 0 # 탐색한 배추는 0으로 갱신

    # 동서남북 탐색
    search(x+1,y)
    search(x,y+1)
    search(x-1,y)
    search(x,y-1)


for _ in range(T):
    N, M, K = map(int, input().split()) # 가로길이, 세로길이, 배추 수
    graph = [[0] * N for _ in range(M)]

    result = 0 # 지렁이 수

    # 그래프 생성
    for _ in range(K): # 배추 수 만큼 반복
        a,b = map(int,input().split())
        graph[b][a] = 1 # 배추 위치 표기

    # dfs
    for i in range(M):
        for j in range(N):
            if graph[i][j] == 1: # 배추가 존재하는 경우
                search(i,j) # 인접 배추 탐색
                result += 1 # search가 종료하면, 지렁이 수 추가

    print(result)

 

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)

IDEA