[ 파이썬(python) ] 이것이 코딩 테스트다 - 음료수 얼려먹기(DFS)

📌 이것이 코딩 테스트다 - 음료수 얼려먹기

영상 링크(42:48)

---

💡 나의 풀이

DFS로 문제를 해결 할 수 있는데, 0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶으면 된다.
BFS, DFS는 조건 설정이 중요한 것 같다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴보고 주변 지점 중 값이 0이면서 아직 방문하지 않은 지점이 있으면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3. 1~2번의 과정을 모든 노드에 반복하고, 방문하지 않은 지점의 수를 센다.

'''
4 5
00110
00011
11111
00000
'''

'''
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
11111111110011
11100011111111
11100011111111
'''

def dfs(x, y):
    if x <= -1 or y <= -1 or x >= N 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 = []
cnt = 0

# 입력받기
for i in range(N):
    graph.append(list(map(int, input())))

# 모든 좌표 입력
for i in range(N):
    for j in range(M):
        if dfs(i, j) == True:
            cnt+=1
print(cnt)