[알고리즘] - 음료수 얼려 먹기 (이코테 실전 문제)

• 이번 문제는 이것이 취업을 위한 코딩 테스트다 with 파이썬 속 실전 문제 ‘음료수 얼려 먹기’ 입니다. 문제 명세 및 입출력 예시는 해당 책을 참고해주세요!

접근 방식

• 해당 문제는 기본적으로 DFS를 활용하여 얼음 틀에서 숫자 0인 부분들에 대해 탐색을 진행하고, 한 번 탐색 시 더 이상 탐색이 불가능할 때까지 탐색을 한 뒤, 이러한 탐색이 총 몇 번 이뤄졌는지 확인하는 방식으로 해결할 수 있었습니다.
• 기본적인 DFS 코드에 탐색 과정에서 숫자가 0일 때만 탐색을 진행하는 방식으로 구현을 진행했습니다.

구현

• 기본적인 DFS 코드에 문제의 조건을 추가하여 재귀 함수를 호출하여 탐색하는 과정에서 아래와 같은 코드를 추가했습니다.

      # 갈 수 있는 곳은 상하좌우
      steps = [(-1,0), (1,0), (0,1), (0,-1)]
        
      # graph를 살펴 보며 갈 수 있는 곳 중 아직 안 간 곳으로 재귀함수 호출
      for step in steps:
          cur_x = i + step[0]
          cur_y = j + step[1]
    
          # graph의 인덱스를 벗어나지 않는지 체크
          if cur_x < 0 or cur_x >= length or cur_y < 0 or cur_y >= width:
              continue
    
          # 0인데 아직 방문되어 있지 않은 곳은 방문
          if graph[cur_x][cur_y] == 0 and not visited[cur_x][cur_y]:
              dfs(graph, (cur_x, cur_y), visited, length, width)
  

  • graph를 탐색하는 과정에서 갈 수 있는 곳은 상, 하, 좌, 우로 제한되기 때문에 상, 하, 좌, 우를 표현하기 위해 steps 배열을 정의하고, 이를 순회하며 네 방향에 대한 탐색을 진행했습니다.
  • 또한 상, 하, 좌, 우를 탐색하는 과정에서 graph의 인덱스 범위를 벗어나는 경우가 발생할 수 있기 때문에, 이에 대한 체크를 진행했습니다.
  • 마지막으로 방문 조건에 graph의 해당 인덱스의 값이 0인 경우만 방문 하도록 했습니다.

트러블 슈팅

• 위와 같이 구현을 진행하는 과정에서, 이상하게도 마지막 조건인 아래의 코드가 제대로 수행되지 않았습니다.

  # 0인데 아직 방문되어 있지 않은 곳은 방문
  if graph[cur_x][cur_y] == 0 and not visited[cur_x][cur_y]:
      dfs(graph, (cur_x, cur_y), visited, length, width)
  

• 그 이유를 고민하던 중, dfs 함수에 graph로 전해지는 배열(ices)은 아래와 같은 방식으로 입력을 받고 있었는데, 이 부분에 문제가 있음을 확인했습니다.

  for i in range(length):
      ices.append(list(input().rstrip()))
  

  • 기본적으로 입력으로 주어지는 11100011111111.. 과 같은 숫자들은 문자열의 형태로 주어지고 있었습니다.
  • 따라서 위와 같은 방식으로는 ices의 원소들이 0, 1이 아닌 ‘0’, ‘1’ 이라는 char 형을 갖게 되었습니다.

• 이에 따라 문자열들을 map 함수를 이용해 정수형으로 변환하여 입력을 받도록 수정했습니다.

  for i in range(length):
      ices.append(list(map(int, input().rstrip())))
  

• 그 결과 위의 구현 코드가 정상적으로 잘 작동하는 것을 확인할 수 있었습니다.

전체 코드

• 구현한 전체 코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

def dfs(graph, cur_tup, visited, length, width):
    i, j = cur_tup

    # 방문 처리
    visited[i][j] = True

    # 갈 수 있는 곳은 상하좌우
    steps = [(-1,0), (1,0), (0,1), (0,-1)]

    # graph를 살펴 보며 갈 수 있는 곳 중 아직 안 간 곳으로 재귀함수 호출
    for step in steps:
        cur_x = i + step[0]
        cur_y = j + step[1]

        # graph의 인덱스를 벗어나지 않는지 체크
        if cur_x < 0 or cur_x >= length or cur_y < 0 or cur_y >= width:
            continue

        # 0인데 아직 방문되어 있지 않은 곳은 방문
        if graph[cur_x][cur_y] == 0 and not visited[cur_x][cur_y]:
            dfs(graph, (cur_x, cur_y), visited, length, width)

length, width = map(int, input().rstrip().split())
ices = []

for i in range(length):
    ices.append(list(map(int, input().rstrip())))

# check 여부를 확인하기 위한 배열 초기화
check = [[False] * width for _ in range(length)]

# dfs를 한 번 탐색할 때마다 1씩 아이스크림 개수를 증가시킴
icecream = 0

for i in range(length):
    for j in range(width):

        # 방문하지 않은 것들 중, 원소가 0일 경우만 탐색
        if not check[i][j] and ices[i][j] == 0:
            icecream += 1
            dfs(ices, (i, j), check, length, width)

print(icecream)

Lesson

사실 처음 입력 받을 때 주의를 기울였다면 크게 문제가 되지 않았어야 할 부분에 대해서 신경을 쓰지 못하다 보니 구현 이후의 디버깅을 하는 과정에서 시간을 더 오래 쓰게 된 것 같습니다. 기본적으로 숫자와 문자열 자료형 사이의 비교가 발생하면 당연히 runtime 에러를 발생 시킨다고 생각했던 것이 문제였던 것 같습니다. 예컨대 아래의 코드를 실행하는 과정에서, 만약 graph에 담긴 원소가 문자열 자료형이었다면, 당연히 실행 과정에서 런타임 에러를 발생 시킬 줄 알고, 해당 부분이 잘못되었다는 생각을 갖지 못해 디버깅 과정이 조금 더 오래 걸렸던 것 같습니다.

# 0인데 아직 방문되어 있지 않은 곳은 방문
if graph[cur_x][cur_y] == 0 and not visited[cur_x][cur_y]:
    dfs(graph, (cur_x, cur_y), visited, length, width)

아직 python 언어에 대해서 공부할 부분이 많다는 것을 느끼며.. python 언어를 사용하며 실수했던 지점들을 모아서 한 번 포스팅을 올려야겠습니다. 화이팅..!