음료수 얼려 먹기 python - [이코테/DFS, BFS 알고리즘]

문제 내용 요약

DFS, BFS를 공부하던중 '동빈나'님의 자료를 보며 DFS, BFS를 공부했다.해당 문제에대한 해석에는 DFS를 통한 풀이방법만 제시해서 BFS로도 풀줄 알아야될거 같아서 BFS로 만들어 풀어봤다.

문제 원리파악

일단 이 문제에서 숫자 0끼리 묶여있는 그래프라고 생각하고, 연결이 되어있지 않은 총 그래프의 갯수를 생각한다. 위 그림에서는 총 3개의 그래프를 만들 수 있다.

위의 입력 맵을 예시로 [x,y]값을 [0,0]부터 [3,4]까지 순차탐색하면서 최초 0을 방문하면 연결된 그래프를 모두 1로 바꾸고, Count 1을 더하는 방식으로 진행한다.

만약 순차탐색을 하면서 grpah[x,y]값이 1일 경우 Pass하는 방식으로 코드를 진행하면 원하는 문제의 답이 나올 것이라고 생각한다.

 

코드(DFS)

DFS방식은 저자님께서 친철하게 설명해주신다. 유튜브의 '이코테 DFS & BFS'만 참고해도 이해 할 수 있을 것이다.

def dfs(x, y, graph):
    # 위치에서 벗어날 때는 False
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    # 현재 위치가 방문하지 않은 곳 0 일때
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x - 1, y,graph)
        dfs(x + 1, y, graph)
        dfs(x, y - 1, graph)
        dfs(x, y + 1, graph)
        return True
    return False


ice_list = [
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]

n = 4
m = 5

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

print(count)

코드(BFS)

BFS방식은 따로 안나와서 직접 풀어보았다.

최적의 방식으로 푼지는 모르겠으나..생각나는 대로 풀었다.

from collections import deque


def bfs(graph, x, y):
    print(x,y)
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    
    count = 0
    if graph[x][y] == 1:
        return False
    else:
        queue = deque([x,y])
        graph[x][y] = 1
        count += 1

    while queue:
        print(queue)
        x_1 = queue.popleft()
        y_1 = queue.popleft()

            
#         print(x_1 + 1, y_1, graph[x_1 + 1][y_1])
#         print(x_1, y_1 + 1, graph[x_1][y_1 + 1])
        
        # 아래로 이동일때 조건
        # x_1의 칸이 넘어갈 경우 패스
        if x_1 + 1 >= n:
      
            None
        else: 
            if graph[x_1 + 1][y_1] == 0:
                queue.append(x_1 + 1)
                queue.append(y_1)
                graph[x_1 + 1][y_1] = 1
        
        # 오른쪽으로 이동일때 조건
    	# y_1의 칸이 넘어갈 경우 패스
        if y_1 + 1 >= m:
            None
        else:
            if graph[x_1][y_1 + 1] == 0:
                queue.append(x_1)
                queue.append(y_1 + 1)
                graph[x_1][y_1 + 1] = 1
        
        print(graph)
    return 1

graph = []

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

for i in range(n):
    graph.append(list(map(int, input())))
    
    
count = 0
for i in range(n):
    for j in range(m):
        if bfs(graph,i,j) == 1:
            count += 1
            
print(count)

깨달은점

이 문제를 풀때는 [0,0]에서 시작해서 오른쪽 탐색 조건과 아래쪽 탐색 조건만 만들어서 풀어도 문제의 조건을 만족했지만 향후 위쪽과 왼쪽을 탐색하는 조건이 나올경우의 문제도 생각해야 할 수도 있을거라고 생각한다.