DFS - 음료수 얼려 먹기

이코테 p.149

 

N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 있는 부분은 1로 표시된다.

구멍이 뚫린 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

 

입력 조건

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

출력 조건

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

---

기록

 

1. 상하좌우로 탐색하는 dfs함수 구현

2. 각 칸에 대하여 dfs를 수행하고, 그 칸이 방문하지 않은 곳이면 result값을 1 증가시킴

3. dfs를 수행하면서 방문한 곳은 값을 1로 변경하여 재방문하지 않도록함

 

이러면 덩어리덩어리 묶어서 개수를 셀 수 있다.. 

dfs수행하면서 지나간 곳은 1로 막아버리니 0으로 연결돼있는 칸은 카운트가 단 한번만 오르게되기 때문..

 

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

def dfs(x,y):
    if x<0 or y<0 or x>=n or y>=m:#맵 바깥으로 나가면 실행중단
        return False
    if graph[x][y]==0: #현재위치가 방문하지 않은 곳이면 상하좌우로 dfs 수행
        graph[x][y]=1 #방문처리. 1로변경하여 다음번에 방문하지 않도록 함
        dfs(x+1,y)
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True 
    return False

result=0
for i in range(n):
    for j in range(m):
        if(dfs(i,j)==True): #각 칸에 dfs를 수행.. 
            result+=1

print(result)

응..