음료수 얼려 먹기 - dfs [21]

문제 설명

• N × M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다.
• 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다.
• 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요.
• 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성됩니다.

---

입력 조건

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

---

출력 조건

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

-test case

• 입력예시 4 5 00110 00011 11111 00000
• 출력 예시 3

---

해결방법

DFS 혹은 BFS로 해결 가능하다.
DFS를 활용하여 해결하려면.

1. 특정한 지점의 상하좌우를 살펴보면서 값이 아직 0이면서 방문하지 않은 지점이 있다면 그 지점을 방문한다.
2. 방문한 지점에서 위를 반복하면 연결된 모든 지점을 방문할 수가 있다.
3. 모든 노드에 대해서 1-2번의과정을 반복하면서 카운트 하면, 서로 떨어진 모든 지점의 개수를 알수 있다.

---

solution

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,y-1);
        dfs(x+1,y);
        dfs(x,y+1);
        return True;
    return False;

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

#모든 노드에 대하여 음료수 채우기
result =0;
for i in range(n):
    for j in range(m):
        #현재 위치에서 DFS수행
        if(dfs(i,j) == True):
            result+=1;

print(result);

---