[python]DFS-冷凍飲料

＜問題＞冷凍飲料

入力条件

の第1行は、氷フレームの長手方向長さNおよび横方向長さMを与える.(1 <= N, M <= 1000)

の第2列からN+1列まで氷棚の形状が与えられる.

この場合、穿孔された部分は0であり、そうでなければ1である.

しゅつりょくじょうけん
一度に作れるアイスクリームの数

を出力します.

嗄嗄嗄嗄嗄嗄嗄嗄
4 5よよよよよよよよよよよ3
00110
00011
11111
00000

<ソリューション>DFSの利用

特定の場所の周囲を上下左右に表示します.周囲の場所の値が0でアクセスされていない場合は、その場所にアクセスします.

アクセスポイントで上、下、左、右を再度表示すると、すべての接続ポイントにアクセスできます.

のすべてのノードを1～2回繰り返し、アクセスされていないポイントの数をカウントします.

def dfs(x,y):
  # 주어진 범위를 벗어나는 경우에는 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 0:
    # 해당 노트를 방문 처리
    graph[x][y] = 1
    # 상,하,좌,우의 위치들도 모두 재귀적으로 호출
    dfs(x-1,y)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True
  return False
# N,M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int,input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
# [[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]
for i in range(n):
  graph.append(list(map(int,input())))

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS수행
    if dfs(i,j) == True:
      result += 1

print(result)

ソース
これがPython(https://youtu.be/PqzyFDUnbrY)による符号化テストである.
https://covenant.tistory.com/132