[알고리즘]DFS/BFS_음료수 얼려먹기(파이썬 재귀함수)

['음료수 얼려먹기' 문제 설명]

-난이도 : ★☆☆

-풀이시간 : 30분

-시간 제한 : 1초

-메모리 제한 : 128MB

-기출 : 이것이 코딩테스트다 p.149

-출처 : 이것이 코딩테스트다

 

-문제 : 

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

00110
00011
11111
00000

-입력조건 :
첫 번째 줄에 얼음 틀의 세로 길이 n과 가로 길이 m이 주어진다. (1<=n,m<=1,000)
두 번째 줄부터 n+1번째 줄까지 얼음 틀의 형태가 주어진다.
이대 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

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

 

 

-입력예시1

4 5
00110
00011
11111
00000

-출력예시1

3

 

 

['음료수 얼려먹기' 답안1]

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

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

#DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x,y) :
    #주어진 범위를 벗어나는 경우에는 즉시 종료
    if x<=-1 or x>=n or y<=-1 or y>=m :
        return False

    #현재 노드를 아직 방문하지 않았다면
    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
    return False


#모든 노드(위치)에 대하여 음료수 채우기
result=0

#n*m행렬에 대하여
for i in range(n) :
    for j in range(m) :
        #현재 위치에서 DFS수행
        if dfs(i,j) == True :
            result+=1

▲답안1 설명

책참고!

 

 

[파이썬]

파이썬 재귀함수를 어떻게 사용하였는지 위 코드에서 공부해보자!