[BOJ 2638]チーズ(python)

11046 ワード
BFS DFS boj テキストリンク
質問する
チーズ漢対訳辞典
問題の説明
BFSまたはDFSを利用する問題.チーズからBFS、DFSは答えがなく、肝心なのはチーズのエッジを利用して空でなければならず、エッジからナビゲーションを行うことです.これでチーズの内部の空間はチェックされません.
  • エッジから四方向探索が開始される.
  • チーズを発見した後、+1を行い外部接触を検査した.
  • 地図で3以上(元チーズ1,接触2以上)の値が見つかった場合は0とする.
    • プールコード
    import sys
import copy
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
cheeze = 0
answer = 0

for _ in range(n):
    graph.append(list(map(int, input().rstrip().split())))

# 치즈 개수 세기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cheeze += 1


def search(arr):
    q = deque()
    global cheeze, answer, n, m
    visited = [[False] * m for _ in range(n)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    q.append((0, 0))
    visited[0][0] = True
    # 바깥에서부터 4방 탐색 시작
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] >= 1:  # 치즈가 있으면 +1
                    arr[nx][ny] += 1
                if not visited[nx][ny] and arr[nx][ny] == 0:
                    visited[nx][ny] = True
                    q.append((nx, ny))
    for i in range(n):
        for j in range(m):
            if arr[i][j] >= 3:
                graph[i][j] = 0
                cheeze -= 1
    answer += 1


while cheeze != 0:
    search(copy.deepcopy(graph))
print(answer)
    [Swift]DFSアプリケーション
    Array.from()