음료수 얼려 먹기

• 문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다.

• 코드

  n,m = map(int, input().split())
  
  graph = []
  
  for _ in range(n):
    graph.append(list(map(int,input())))
  
  def dfs(x, y):
  
  	#그래프 이탈 시
    if x <= -1 or y <= -1 or x >= n or y >= m:
      return False
  
    if graph[x][y] == 0:
      graph[x][y] = 1
  
      # 상하좌우 위치도 체크
      dfs(x-1,y)
      dfs(x+1,y)
      dfs(x,y-1)
      dfs(x,y+1)
      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)

• 문제 풀이

dfs 깊이 우선 탐색 알고리즘을 사용하여 풀었다.

(0,0) 위치부터 상,하,좌,우를 탐색하면서 graph[?][?] 를 1로 바꾸어준다.

때문에 이중 for문에서 다음 dfs(i,j) == Ture 의 코드에서는 False를 반환해 result에 1 더하지 않는다.

결국 첫번째 0에서만 True 를 반환한다. (첫번쨰 0 로직에서 주변 0인 애들을 모두 1로 바꿔주었기 때문)

이후 계속 이중 for문을 수행하다 다시 0을 발견할 시 다시 주변 0 들을 모두 1로 바꾼 후 result 에 1을 더해주어 음료수를 얼릴 수 있는 개수를 구한다.

(결국 마지막 graph 의 원소는 모두 1를 바뀌어 있을 것이다.)