음료수 얼려 먹기

음료수 얼려 먹기

문제

N x M 크기의 얼음 틀이 있다.

구멍이 뚫린 부분은 0, 칸막이는 1 이다.

만들 수 있는 총 아이스크림의 개수는?

첫 번째 줄에 세로길이 N 과 가로길이 M 이 주어진다

1 <= N, M <= 1,000

입력 예시

4 5

00110

00011

11111

00000

출력 예시

3

정답

이 문제는 DFS를 이용하면 간단히 해결할 수 있다.

코드는 다음과 같다.

n, m = map(int, input().split()) # n: 세로, m: 가로 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] graph = [] for i in range(n): graph.append(list(map(int, input()))) 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 # 상하좌우의 위치도 모두 재귀적으로 호출 for i in range(4): tx = x + dx[i] ty = y + dy[i] dfs(tx, ty) return True return False # 모든 노드에 대하여 음료수 채우기 result = 0 for i in range(n): for j in range(m): if dfs(i, j) == True: result += 1 print(result)

from http://ympark4.tistory.com/19 by ccl(A) rewrite - 2021-09-22 19:26:48