[이것이취업을위한코딩테스트다] Chap05 - 음료수 얼려 먹기

DFS/BFS 실전문제 - 음료수 얼려먹기

 

위와 같이 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 위와 같은 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

입력조건, 출력조건, 입력예시는 다음과 같다.

 

 

 

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 x >= n or y <= -1 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

result = 0

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

print(result)

 

문제의 접근 방법

 

1) dfs를 활용해 탐색 수행

2) 해당 지점의 인접 노드를 탐색했을 때 0이면(얼음이 될 수 있는 부분)서 방문하지 않은 지점이 있다면 해당 지점 방문

3) 방문한 지점에서 다시 상,하,좌,우를 살피면서 재귀 수행

4) 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.