[ DFS ] 음료수 얼려먹기

음료수 얼려 먹기

문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

입력

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

 

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시2

8

 

정답 코드 

#자료구조 세팅
n, m = map(int, input().split())
graph = []

for i in range(n) :
  graph.append(list(map(int,input())))

# dfs 알고리즘 구현
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
      #상하좌우이동
      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)

 

나의 코드 

maxY, maxX = map(int,input().split())
 # 얼음틀
graph = []
for i in range(maxY) :
  graph.append(list(map(int,input())))

# 방문여부 자료구조
visited = [] 
for i in range(maxX) :
  visited.append([False] * maxY )

#상하좌우 이동 자료구조
dx = [ 0, 0, -1 , 1 ]
dy = [ 1, -1, 0 , 0 ]


# 좌표 검증 함수
def validateIndex(x,y) :
  if x < 0 or x >= maxX or y < 0 or y >= maxY :
      return False
  else : return True 

# DFS 알고리즘 구현 함수 
def dfs(x, y) :
  visited[x][y] = True # 방문처리
  if not validateIndex(x,y) :
    return # 정확한 값을 리턴해야 함수를 사용하는 쪽이 편하다.
  if graph[x][y] == 1 :
    return # 정확한 값을 리턴해야 함수를 사용하는 쪽이 편하다.

  #상하좌우를 for문으로 구현, 
  for i in range(4) :
    tmpX = x+dx[i] #이동 할 x 좌표
    tmpY = y+dy[i] #이동 할 y 좌표

    #좌표 유효성 검사 
    if not validateIndex(tmpX,tmpY) :
      print("부적격 인덱스 : ",tmpX," ",tmpY)
      continue 
    #좌표 방문여부 검사
    if visited[tmpX][tmpY] :
      print("True 이다!",tmpX," ",tmpY)
      continue
    # 조건검사 통과시 함수 수행
    dfs(tmpX,tmpY)

result = 0
for j in range(maxY) :
  for i in range(maxX) :
      #이미 방문한 곳은 재방문X
      if visited[i][j] :
        continue
      dfs(i,j)
      result += 1

print("결과 : ", result)

 

 

자체 리뷰

 

1) 방문여부 자료구조를 하나 더 생성하여 로직이 복잡해졌다. 

=> graph의 값이 0이면 뚫린 곳, 1이면 막힌 곳이다. 뚫린 곳을 막아버리면 방문한 곳을 재방문하지 않으니 자료구조를 하나 더 생성할 필요가 없다. 

 

2) dfs함수가 정확한 결과를 return하지 않아, 코드를 이해하기 힘들어졌다.

=> dfs 결과에 따라 result가 +1이 되는데 dfs가 명확한 값을 return하지 않는다. 

 

3) 상하좌우 이동 시, for문 사용보다 재귀함수를 나열하는 것이 시각적으로 이해하기 쉽다. 

=>  상,하,좌,우 이동할때마다 재귀호출을 해야하는데, for문을 사용했다. 한 가지 방법이기도 하지만 때로는 나열하는게 직관적일 수 있다.

 

 

 

---

 

참고자료 

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서