B)1012

有機白菜

質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.1本の白菜の上下左右4方向に異なる白菜がある場合は隣接しています.
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.0は白菜を植えていない土地を表し、1は白菜を植えた土地を表す.

入力

入力された第1行は、試験例の個数Tを与える.次の行から、各試験例について、第1行は、キャベツ栽培地の横長M(1≦M≦50)および縦長N(1≦N≦50)およびキャベツ栽培場所の個数K(1≦K≦2500)を与えた.次いでK行はハクサイの位置X(0≦X≦M−1),Y(0≦Y≦N−1)を与える.2つの白菜が同じ位置にある場合はありません.

しゅつりょく

各試験箱について、所望の最小白菜白ミミズ数を出力する.
グラフィックの参照
図表探索問題を集中的に解決しているが,問題がどのように解決されるか,少し頭がつかめない.もちろん、グラフィック部分のみ
ミミズは、隣接する白菜に移動することができるので、白菜が集まるエリアでは、ミミズが1匹あれば害虫を全部食べることができます.
つまり、白菜(節点)がこの地にグラフを形成すれば、グラフにミミズが1匹しかなく、害虫が生えないということです.
最終的に、この問題は、畑全体で、白菜の位置を見つけ、白菜から、隣接するノードで探索し、数えて、最終的に必要なミミズの数を知ることです.
実装(DFS)
1.畑(リスト)をブラウズし、値が「1」のインデックスを検索します.
2.「1」インデックスでDFSを行い、カウンタを1つ追加します.
3.畑を全面的に探索し、カウンタ値を出力するまで繰り返します.

import sys

sys.setrecursionlimit(10 ** 8)


def dfs(x, y):  # v = 현재 탐색 노드
    global visited
    visited[x][y] = True  # 현재 노드를 방문 처리
    graph[x][y] = 2
    for i in range(4):
        a, b = x + dx[i], y + dy[i] #4방향 탐색
        if 0 <= a < N and 0 <= b < M:
            if not visited[a][b] and graph[a][b] == 1:
            #배추가 심어져있을 경우
                visited[a][b] = True
                dfs(a, b)


T = int(input())
for B in range(T):
    bug = 0 #지렁이 카운터
    M, N, K = map(int, sys.stdin.readline().split())

    graph = [[0] * (M) for _ in range(N)]

    visited = [[False] * (M) for _ in range(N)]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    for i in range(K):  #배추 위치
        x, y = map(int, sys.stdin.readline().split())
        graph[y][x] = 1

    for a in range(N):
        for b in range(M):
            if graph[a][b] == 1:
                dfs(a, b) #dfs가 진행되면 지렁이 수 +1
                bug += 1

    print(bug)

グラフィック検索問題でよく見られる四方向検索(東西南北)程度を覚えておくと、他のアルゴリズムを扱うときにも便利だと思います.