[DFS/BFS] ▲ 문제1 - 음료수 얼려 먹기(149p)

[이코테] 문제1 - 음료수 얼려 먹기

풀이 시간: 30분 이내 

 

1) 문제 해결 아이디어

이 문제는 DFS 혹은 BFS로 해결 가능하다.

특정 지점에서 DFS/BFS를 수행하여 이동 가능한 모든 지점에 대해 방문 처리를 한다.

dfs 문제는 재귀 함수를 이용하여 해결한다.

 

재귀 함수의 종료 조건은 해당 좌표가 범위를 벗어났을 경우다.

현재 좌표를 아직 방문하지 않았다면 방문 처리를 하고 상하좌우에 해당하는 좌표를 매개변수로 하여 dfs를 호출한다.

 

<동작 과정>

1. 해당 지점이 아직 방문하지 않은 곳이라면 방문 처리

2. 상하좌우 지점 재귀 호출로 탐색

 

2) 소스코드

n, m = map(int, input().split())  # 세로, 가로
graph = [list(map(int, input())) for _ in range(n)]  # n * m
res = 0  # 아이스크림 개수

def dfs(x, y):
  # 인덱스 범위 벗어나면(종료 조건)
  if(x < 0 or x >= n or y < 0 or y >= m):
    return False

  # 현재 좌표를 아직 방문하지 않았다면
  if graph[x][y] == 0:
  	# 1.방문 처리
    graph[x][y] = 1  
    # 2. 상, 하, 좌, 우 재귀 호출로 탐색
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)
    return True
  return False

for i in range(n):
  for j in range(m):
    # 현재 위치에서 dfs 수행이 끝나면
    if dfs(i, j) == True:
      res += 1
      
print(res)