[BOJ] 1012번 유기농 배추 / 사용언어 : 파이썬(python)

※ 문제링크

1012번: 유기농 배추

해당문제는 DFS와 BFS를 사용하여 해결할 수 있는 문제였다. 단순하게 상, 하, 좌, 우에 연결되어 있는 배추의 위치들을 활용하여 연결된 그래프의 수가 몇개인지 구하면 되는 문제였기에 크게 어렵지 않게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 바탕으로 2차원 배열로 배추밭을 구현한다.

2. DFS 또는 BFS를 사용하여 연결된 배추들을 확인할 함수를 작성한다.

3. 2중 반복문을 활용하여 배추밭의 모든 위치를 확인하고, 값이 1이면 함수를 적용하고 연결되어 있는 배추들의 집단 수를 체크한다.

4. 결과값을 출력한다.

+ 배열에서 특정값을 확인할 때 x,y의 위치는 일반적인 좌표점과 반대임을 기억하고 코드를 짜야한다.

+ DFS로 코드 작성시 sys함수를 이용하여 재귀한계를 확장시켜줘야함을 기억하자

 

# dfs 풀이
# import sys
# sys.setrecursionlimit(10**6) # 재귀범위 확장
# input = sys.stdin.readlin # 입력값 처리시간 단축을 위한 sys 함수
T = int(input())
cnt_list = []
for _ in range(T):
    M, N, K = map(int, input().split()) # M : 가로 / N : 세로 / 배추위치
    field = [[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        field[y][x] = 1
    dx = [-1, 1, 0 , 0]
    dy = [0, 0, -1 , 1]
    cnt = 0
    def dfs(x, y):
        field[y][x] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if field[ny][nx] == 1:
                    dfs(nx, ny)
    for x in range(M):
        for y in range(N):
            if field[y][x] == 1:
                dfs(x, y)
                cnt += 1
    cnt_list.append(cnt)
print(*cnt_list)

# bfs풀이
import sys
from collections import deque
T = int(input())
cnt_list = []
for _ in range(T):
    M, N, K = map(int, input().split()) # M : 가로 / N : 세로 / 배추위치
    field = [[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        field[y][x] = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    cnt = 0

    def bfs(field, x, y):
        queue = deque()
        if field[y][x] == 1:
            field[y][x] = 0
            queue.append([x, y])
        
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < M and 0 <= ny < N:
                    if field[ny][nx] == 1:
                        field[ny][nx] = 0
                        queue.append([nx, ny])
        return 

    for x in range(M):
        for y in range(N):
            if field[y][x] == 1:
                bfs(field, x, y)
                cnt += 1
    cnt_list.append(cnt)
print(*cnt_list)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.