[python] 백준 1012번 유기농 배추

백준 1012번 유기농 배추

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

문제

풀이

이것이 취업을 위한 코딩 테스트다 with 파이썬 DFS&BFS의 음료수 얼려 먹기와 흡사한 문제.

1 -- 테스트 수
5 3 6 -- m,n,k (m: 열 개수, 가로 | n: 행 개수, 세로 | k: 배추 위치 수
0 2 -- 그래프로 따지면 graph[2][0]과 동일
1 2
2 2
3 2
4 2
4 0

[[0, 0, 0, 0, 1],

[0, 0, 0, 0, 0],

[1, 1, 1, 1, 1]]

import sys
sys.setrecursionlimit(10 ** 6)

T = int(input()) # 테스트 수
def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=m:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0 # 방문 처리
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False

for _ in range(T):
    m,n, k = map(int, input().split()) #열, 행, 배추의 위치
    graph = [[0] * m for _ in range(n)]  # 각 행을 개별적으로 초기화

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

    result = 0
    for i in range(n):
        for j in range(m):
            if dfs(i, j) == True:  # 열과 행의 순서로 dfs 호출
                result += 1

    print (result)

📌 주의

• 재귀 사용 시 import sys 꼭꼭꼭
• 행열 구분 똑바로 하기. x가 세로인지 가로인지...
• 방문처리 까먹지 말기.