[코딩테스트] 유기농 배추

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

문제부터 분석해봅시다

이 문제는 전형적인 dfs/bfs 문제입니다.

입력으로는 배추가 심어진 정보가 들어가고, 출력으로는 필요한 배추지렁이의 개수를 요구하고 있습니다.

이 문제는 이전에 풀었던 연결 요소의 개수 문제와 매우 유사합니다. 그러나 차이점이 하나 존재하는데요, 다음과 같습니다.

간선이 상하좌우 방향이기 때문에 상하좌우로 dfs 탐색을 수행해야한다

따라서 위를 고려하여 코드를 작성하면 다음과 같습니다.

코드를 보겠습니다

import sys
sys.setrecursionlimit(10000)

def dfs(graph, x, y, N, M):
    # 탈출조건
    if x <= -1 or x >= M or y <= -1 or y >= N:
        return False
    
    # 만약에 배추가 심어진 경우
    if graph[x][y] == True:
        # 배추 방문
        graph[x][y] = False
        # 상하좌우 방문
        dfs(graph, x - 1, y, N, M)
        dfs(graph, x + 1, y, N, M)
        dfs(graph, x, y - 1, N, M)
        dfs(graph, x, y + 1, N, M)
        
        return True
    
    return False
    

input = sys.stdin.readline
def sol():
    
    M, N, K = map(int, input().split())

    cabbage_map = [[False for _ in range(N)] for _ in range(M)]

    for _ in range(K):
        x, y = map(int, input().split())
        cabbage_map[x][y] = True

    answer = 0

    for x in range(M):
        for y in range(N):
            if dfs(cabbage_map, x, y, N, M) == True:
                answer += 1
            
    print(answer)
    
for _ in range(int(input())):
    sol()

코드를 설명드리겠습니다. 일단 dfs 함수부터 설명드리겠습니다.

모든 재귀함수가 똑같듯이, dfs라고 특별할 것 없습니다. 무조건 탈출조건부터 앞에 기재해주고, 후에 점화식을 써주면됩니다.

탈출조건의 경우, 주어진 인덱스 범위를 넘어가버리면 바로 탈출하면됩니다. 탐색을 못하기 때문이죠.

그 다음에는 만약에 배추가 심어진 좌표가 파라미터로 들어오게 되는 경우에 일단 해당 좌표를 방문처리를 한 다음에, 상하좌우 방향으로 dfs를 굴려서 죄다 방문처리를 해줍니다. 다음에 True를 반환하게 만듭니다.

만약 배추가 심어진 좌표가 파라미터로 전달이 된게 아니라면, return False를 해주면 되겠죠?

그리고 반복문을 통해 지도 좌표를 하나하나 읽어가면서 dfs를 굴리고 answer를 1 증가시키면 문제는 끝입니다.