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

얼음 틀에 음료수를 넣고 얼렸을 때 나오는 얼음 덩어리는 몇 개인지 세는 문제

- 깊이우선탐색 (Depth-First Search; DFS)

 

(아래의 표가 얼음 틀이라고 가정)

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

0끼리 맞닿아 있는 곳이 하나의 얼음 덩어리, 1 부분에는 음료가 들어가지 않아 얼음이 얼지 않음

 

입력: 

행, 열 순으로 입력이 주어지고, 이후 각 행에 열 개수에 맞는 0과 1의 조합이 주어짐

ex)

4, 5

00110

00011

11111

00000

 

출력: 얼음 개수 출력

3

 

해결 방법:

- 2차원 배열 형태의 그래프로 간주하여 상하좌우로 탐색하면서 0인 부분에서 재귀함수로 다시 탐색

- 1이 나오면 종료하고 전체 함수가 종료되면 True를 반환하고 이후에 함수가 True를 반환하면 얼음 count

 

신경써야 할 사항:

1. 각 행을 입력받으면서 2차원 graph 리스트에 추가할 때

    - 문자열을 input으로 입력받은 후에 list로 바로 캐스팅하면 하나의 문자씩 나누어지면서 list로 생성됨

2. DFS 함수를 만들어서 내부에서 조건이 성립되면 지속적으로 재귀호출

3. 함수 내에서 재귀호출해서 진행하므로 함수가 진행되는 조건은 해당 행렬의 성분에서의 함수 반환값이 True인 경우에 실행되도록 설정

 

코드:

 

N, M = map(int, input().split())

# 얼음틀 모양의 2차원 그래프 생성
graph = []
for i in range(N):
    graph.append(list(map(int, input())))


def check_ice(x, y):

	# 행렬의 범위를 벗어나는 경우의 종료 조건
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False
    
    # 탐색하는 행렬의 성분이 0인 경우 (얼음이 얼 수 있는 곳)
    if graph[x][y] == 0:
    	# 해당 부분 방문 처리
        graph[x][y] = 1
        # 재귀호출로 탐색
        check_ice(x-1, y)   # 상
        check_ice(x+1, y)   # 하
        check_ice(x, y-1)   # 좌
        check_ice(x, y+1)   # 우
        
        return True
        
    return False


ice_count = 0

# 함수 내부에서 0이 아닌 부분에서는 False를 반환하게 되어있으므로 1인 부분은 세지지 않음
for n in range(N):
    for m in range(M):
        if check_ice(n, m):    # (if check_ice(n, m) == True:)
            ice_count += 1

print(ice_count)