[DFS 알고리즘] 음료수 얼려 먹기 - 파이썬(python)

음료수 얼려 먹기

난이도 : 中下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n, m = map(int, input().split())

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

def dfs(x, y):
    if (x <= -1 or y <= -1 or x >= n or y >= m):
        return False

    else:
        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

result = 0

for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result = result + 1

print(result)

---

예시

 

n, m = map(int, input().split())

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

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+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:
            result = result + 1

print(result)

---

해설

먼저 n과 m, graph로 입력을 받습니다. 이 문제는 DFS 알고리즘을 사용합니다.
dfs 함수를 정의하고, dfs 알고리즘을 사용할 것이므로 재귀 함수를 사용합니다.
시작 위치를 1로 바꾸고, 상하좌우에 모두 dfs 함수를 재귀 형식으로 적용하여 붙어있는 칸을 전부 1로 바꿉니다.
전부 1로 바꾼 뒤에, 재귀문에서 빠져 나오면 True를 반환해줍니다.
여기서 True로 반환된 값은 아래 이중 for 반복문에서 result의 값을 증가시켜줍니다.
위와 같은 과정을 for 이중 반복문으로 탐색하고, True 값이 반환되는 횟수 만큼 result 값을 증가시켜주면 됩니다.