음료수 얼려 먹기

1. 문제 설명

출처 : 이코테2021

• 0이 붙어 있는거 끼리 모여 하나의 덩어리를 이룬다.
• 여기서는 총 3개의 덩어리가 만들어진다.

---

2. 문제 조건

• 4(N), 5(M) 즉, 4 * 5 형태의 얼음판이 있다.

---

3. 문제 해결 아이디어

• 3*3이라고 가정할 때 서로 인접한 노드, 그래프 형식으로 만들 수 있다.
• 왼쪽상단을 시작점으로 잡으면 1을 만날때 동안 DFS or BFS로 접근한다.

1. DFS를 활용하여 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문가능
3. 모든 노드에 대하여 1~2번의 과정을 반복하여 결국 방문하지 않은 지점의 수를 카운트한다.

---

4. 풀이

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을 벗어나면 False로 반환한다.
• 그래프의 x,y가 0(방문하지 않았으면) 1로 바꿔주고 재귀호출을 통해 위, 아래, 양 옆으로 이동한다.

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

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

#모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        if DFS(i, j) == True:
            result += 1
print(result)