[코테] DFS/BFS 문제풀기 - 음료수 얼려 먹기

Day9

DF/BFS 문제풀기 - 음료수 얼려 먹기(난이도 중하)

 

<문제>

N X M 크기의 얼음 틀에 뚫린 부분은 0, 칸막이가 있는 부분은 1로 표시되며 구멍이 뚫린 부분은 상, 하, 좌, 우로 붙어 있다면 연결되어 있다고 간주한다. 만들어지는 총 아이스크림의 개수 구하자.

 

<조건>

첫째 줄: N과 M

N줄 : 얼음 틀의 형태. 0 또는 1.

음료수 얼려 먹기 풀기

#솔루션

n, m = map(int, input().split())

ice = []
for i in range(n):
  ice.append(list(map(int, input())))

def dfs(x, y):
  # 범위 밖
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  # 현재 노드가 아직 방문하지 않은 곳이면
  if ice[x][y] == 0:
    ice[x][y] = 1
    # 상하좌우 재귀적으로 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    return True
  return False

# 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    # 현재 위치 DFS 수행
    if dfs(i, j) == True:
      result += 1

print(result)

DFS를 이용해서 연결된 노드들을 묶어야 한다.

어떤 지점에서 상, 하, 좌, 우를 살펴보았을 때에 0인 곳으로 가고, 그곳을 1로 바꾼다. 또 그곳에서 상, 하, 좌, 우를 살펴보며 연결된 곳들을 모두 방문한다. 

 

#1

#2