[나동빈 코딩테스트] DFS 문제 (얼음과자 만들기)

#나동빈 DFS 문제 - 얼음과자 만들기

#난이도 : 중상

 

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

ice_map = []  # 0이면 얼음, 1이면 틀
for _ in range(n):
  new_line = list(map(int, input().split()))
  ice_map.append(new_line)

def dfs(i,j): # 세로, 가로 순. dfs 탐색을 통해 얼음과자 1개 만듬. (덩어리)
  if i < 0 or i >= n: # 범위 밖이면 return
    return 
  if j < 0 or j >= m: # 범위 밖이면 return
    return

  if ice_map[i][j] == 1: # 원래 1이었던 구간
    return False
  else: # 새로이 찍은 점 (1이 아니었던 구간)
    ice_map[i][j] = 1 # 방문한 곳은 1로 표시. (추후 재방문 불가하도록 만들기 위해서)
    dfs(i-1,j) # 상하좌우 탐색
    dfs(i+1,j)
    dfs(i,j-1)
    dfs(i,j+1)
    return True # 얼음과자 1개 완성

count = 0
for i in range(n):
  for j in range(m):
    if dfs(i,j) : #ice_map을 하나씩 찍어가면서 DFS 탐색. True를 return한다면 count + 1
      count+=1
  
print(count) #총 얼음 과자의 개수

 

# 시간 복잡도 : O(NM) 

# 인접 리스트를 활용하지 않고 2차원 공간에서의 DFS를 적용해야 한다는 것이 핵심.

# 특히 과자를 세는것이 목표인 만큼 탐색 과정이 끝난 후 True를 return 하는 함수를 따로 짜야했음.

# 탐색 자체가 불가능한 경우 False를 return하는 조건도 필요함.

# 주어진 2차원 공간을 최대한 잘 이용하는 것(visited 표시)이 효율적인 해결책이었음.

# 전반적으로 IDEA를 떠올리기 쉽지는 않았음.