[DFS/BFS] (이코테) 음료수 얼려 먹기 - 파이썬(Python)

개요

source : Chapter5 DFS/BFS 음료수 얼려 먹기 149p

문제

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

# 출력
3

• 예제 2

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

# 출력
8

풀이

아이디어

• DFS로 하나의 깊이 우선 탐색이 끝나면 카운트 해주자 (BFS로도 풀 수 있음)
• NxM graph에 방문처리를 바로 해주면 loop는 O(NxM) 만큼 돌지만 이미 방문했으니 skip
• 종료조건
  1. 얼음 틀에서 벗어 남
  2. 값이 1인 칸에 도달
• 성공조건 : 값이 0인 칸

코드

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

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

def ice_dfs(x,y):
    # 종료조건 1
    if x<0 or x>=N or y<0 or y>=M:
        return False  

    # 성공조건  
    if graph[x][y]==0:
        graph[x][y]=1
        ice_dfs(x,y-1) # 좌
        ice_dfs(x,y+1) # 우
        ice_dfs(x-1,y) # 상
        ice_dfs(x+1,y) # 하
        return True
      
    # 종료조건 2
    return False    
    
result=0
for i in range(N):
    for j in range(M):
        if ice_dfs(i,j):
            result+=1
print(result)

메모

• DFS는 stack 구조로 First Input의 결과가 하위 재귀호출이 끝난 후에 반환됨을 기억해야함
• 여기서는 위에서 정의한 return 값이 헷갈렸음
• 즉, 다시 이해해보면
  • 0,0에서 시작하면 성공조건을 타고 상하좌우에 대해 각각 재귀호출에 들어간다.
  • 방문처리가 되면서 하위 호출들이 모두 종료조건에 걸림
  • (우->하->(좌),(우))
  • 다시 타고 올라오면서 True값을 return하지만 값은 최종값인 1개만 리턴

시작점인 (0,0)에 대해서 재귀호출을 하는 세부적인 사항은 아래와 같다.

ice_dfs(0,0)

# 초기 그래프
[[0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]


# ice_dfs(0,0) -> 시작 iter 0
[[1, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]

#ice_dfs(0,1) -> 우 recur 1
[[1, 1, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]

#ice_dfs(1,1) -> 하 recur 2
[[1, 1, 1, 1, 0],
 [0, 1, 0, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]

#ice_dfs(1,0) -> 좌 recur 3
[[1, 1, 1, 1, 0],
 [1, 1, 0, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]

True # recur 3 종료

#ice_dfs(1,2) -> (recur2에서) 우 recur 4
[[1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0]]

True # recur 4 종료
True # recur 2 종료
True # recur 1 종료
True # recur 0 종료

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈