[Algorithm] DFS/BFS - 3

[음료수 얼려먹기]

 

NxM 크기의 얼음 틀이 있음

구멍이 뚫린 부분 : 0, 칸막이가 존재하는 부분 : 1

구멍이 뚫려있는 부분 끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주

얼음틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성

 

해당 얼음틀에서 만들 수 있는 아이스크림은 총 3개

 

[해설코드 - 거의 코드 참고하였음]

- 먼저, 입력받는 리스트를 그래프로 지정

- 끝까지 탐색해야 되는 문제는 DFS 사용 (재귀로 사용하면 탐색이 효과적인듯)

- 먼저, (0,0)부터 대체로 시작인데 해당 위치가 얼음틀인지 아닌지 확인

- 얼음 틀이라면, 해당 부분을 1로 바꿔주고 상하좌우 위치를 바꿔서 dfs함수 실행

- 사실 이 부분이 재귀의 사용 부분인데, 나는 여기서 for문을 4방향으로 탐색 할 뻔했다

이게 바로, 구현 + 탐색 문제가 나오는 이유인듯..

여기서 손쉽게 dfs함수를 재귀로 사용해 주기만 하면 탐색이 된다

 

- 기본적으로 return False를 지정해놔야 재귀를 탈출 할 수 있음

- 만약 네 방향 다 돌고 나서 마지막으로 return True 코드를 실행한다면 0으로 시작되는 칸의 한 덩어리를 다 훑었기 때문에 아이스크림 개수 +1 해 줌

- 어차피, 좌표 대로 움직이기 때문에 헷갈리지 않음

 

[코드]

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

graph = []
for i in range(n): ## 이미 여기서 stack, list 만든거임
    graph.append(list(map(int, input()))) ## split을 안하면 입력할때 띄어쓰기로 입력 안해도 됨

## 재귀로 푸니깐 굳이 pop같은거 안해도 됨

print(graph)

result = 0

def dfs(x,y):
    
    if x>= n or x < 0 or y >= m or y <0:
        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 ## 종료


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

print(result)