[DFS] 이코테 “음료수 얼려 먹기” Python 풀이

문제

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

입력 조건

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

출력 조건

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

입력 예시

4 5
00110
00011
11111
00000

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

출력 예시

3

8

풀이

• Stack 을 사용하지 않고, 재귀 함수를 통한 방문 처리만으로도 해결할 수 있습니다.

예제 코드

# N, M을 공백으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
ice_board = []
for i in range(n):
    ice_board.append(list(map(int, input())))

# 상하좌우 진행용 방향 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 아이스크림 개수
count = 0

# dfs를 통해 현재 노드를 방문한 뒤, 연결된 모든 노드들을 방문
def dfs(start_x, start_y):

    # 현재 노드를 방문 처리
    ice_board[start_x][start_y] = 1

    # 현재 노드와 인접한 모든 노드들을 탐색하며, 방문 가능할 경우 방문
    for i in range(4):

        # 인접 노드 좌표
        nx = start_x + dx[i]
        ny = start_y + dy[i]

        # 인접 노드가 얼음판 내부에 위치할 경우
        if (nx >= 0 and nx < n and ny >= 0 and ny < m):

            # 인접 노드에 음료수를 채울 수 있는지 확인
            if (ice_board[nx][ny] == 0):

                # 인접 노드 방문
                dfs(nx, ny)

# 모든 위치에 음료수 채우기
for i in range(n):
    for j in range(m):
        # 해당 노드에 음료수를 채울 수 있다면
        if (ice_board[i][j] == 0):
            # 해당 노드에서 dfs 탐색 시작
            dfs(i,j)
            count += 1

print(count)

참고

• 이것이 취업을 위한 코딩 테스트다. with python