[이코테/Python] DFS/BFS - 음료수 얼려 먹기

이코테

DFS/BFS 음료수 얼려 먹기(Python)

문제

N x M 크기의 얼음 틀이 있다.
구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있을 경우 서로 연결되어 있는 것으로 간주한다.
이때 생성할 수 있는 총 얼음의 개수를 구하라.

• 예시
  

입력 :
[0,0,1,1,0]
[0,0,0,1,1]
[1,1,1,1,1]
[0,0,0,0,0]
결과 : 3

풀이

이 문제는 0이 연결되어 있는 부분들을 모두 찾아야된다. 그렇기 때문에 하나에서 연결된 부분의 끝까지 탐색하는 DFS(깊이우선탐색) 방법으로 접근하면 쉽게 풀 수 있다.

1. 문제의 입력으로 주어진 그래프를 2중 반복문을 사용하여 모든 인자값을 탐색한다.
2. dfs 함수를 호출하여 해당 인자값으로부터 시작해서 얼음틀이 어디까지 연결되어 있는지를 체크한 후 1로 변경한뒤 전체 결과값에서 +1을 해준다.
3. dfs 함수는 재귀함수 형식으로 호출되며, 탐색을 시작한 값에서 상,하,좌,우 를 탐색하는 방식으로 dfs 함수를 재귀로 호출하여 체크해준다.

새로 알게된 문법

새로 알게된 ‘문법’ 까지는 아니지만, DFS/BFS를 배울 때 해당 예시로 그려진 그래프와 같은 그래프에만 적용되는 줄 알았다. 하지만 해당 문제 처럼 상하좌우를 강제적으로(ex.[x-1,y],[x,y+1]) 형식으로 조회하여 찾을 수 있다는 것을 알게 되었다. 하지만 이렇게 풀 경우 반복문을 세번이나 돌게 되면서 n^3인데 시간초과가 나지 않는 것이 조금 신기하다… 해당 부분은 조금 더 공부가 필요해보인다.

코드

    def solution(graph):
        result = 0
        for i in range(len(graph)):
            for j in range(len(graph[0])):
                # 현재 위치에서 DFS 수행
                if dfs(i, j, graph) == True:
                    result += 1
    
        print(result)
    
    
    def dfs(x, y, graph):
    
        # 주어진 범위를 벗어나는 경우에는 즉시 종료
        if x <= -1 or x >= len(graph) or y <= -1 or y >= len(graph[0]):
            return False
    
        # 현재 노드를 아직 방문하지 않았다면
        if graph[x][y] == 0:
            graph[x][y] = 1
            dfs(x-1, y, graph)
            dfs(x, y-1, graph)
            dfs(x+1, y, graph)
            dfs(x, y+1, graph)
            return True
    
        return False
    
    
    if __name__ == "__main__":
        graph = [
            [0,0,1,1,0],
            [0,0,0,1,1],
            [1,1,1,1,1],
            [0,0,0,0,0]
        ]
    
        solution(graph)