[이코테] 음료수 얼려 먹기 - 파이썬

문제

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

 

다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

입력 조건

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

 

출력 조건

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

 

 

입출력 예시

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

출력
8

---

풀이

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

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


def dfs(x, y):
    
    # 그래프 범위 밖의 인덱스이면 False 반환
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    
    # 그래프 상의 인덱스 위치가 0 이라면 상하좌우 체크
    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

count = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            count += 1
            
print(count)

DFS 를 활용한 문제이다.

인접한 0 에 대해서 깊게(DFS) 0이 안나올때까지 상하좌우를 스캔한 뒤 1 밖에 없을 때 재귀함수에서 탈출한다. 메인 코드에서 0,0 인덱스부터 차근차근 함수를 호출하여 방문을 확인(1로 변경)한다. 물론 1인 경우에는 바로 False 로 반환되었다. 만약 0 이라면 상하좌우가 0인지 1인지 파악하는 dfs( ) 함수를 다시 호출한다. 그래프 크기를 넘는 인덱스가 들어가면 False를 반환하게 된다.

 

본격적으로 BFS/DFS 를 공부하고 있는데 알면 알수록 재미있는게 알고리즘인 거 같다...

백준 홈페이지를 통해서 더 풀어봐야겠다.