[DFS] 틀 모양의 아이스크림 찍어내기

문제

0과 1로된 2차원 배열 모양의 아이스크림 판이 있다. 

0인 부분은 뚫려 있고 1인 부분은 뚫려있지 않은 아이스크림 판이다.

이 판을 아이스크림에 올리면 모양이 나오게된다

예를 들어서 )

00001111

00111000

111000111

처럼 판이 생겼다면 두개의 아이스크림 탄생한다

아이스크림의 개수를 구하는 알고리즘을 만들라

 

해결

하나의 모양을 만들려면 0들이 이어져야 한다. 이어진 0들을 찾기 위해서는 0을 하나 발견했을 때 위/오/왼/아래 방향으로 탐색하여 0이 있는지 확인하며 꼬리에 꼬리를 물고 늘어져야 한다.

단, 모양이 여러개 나올 수 있기 때문에 우리는 모든 틀 하나하나를 다 봐야한다

그러기 위해서는 visited를 만들어서 이미 방문한 노드는 다시 방문하지 않고 넘어갈 수 있도록 조치를 해놓아야 한다. 안 그러면 무한 loop에 빠질 수 있다

 

1차시도

 

# N - 얼음틀 세로 길이 M - 얼음틀 가로 길이
N, M = map(int, input().split())

graph = []
visited = [[False]*(M+1) for _ in range(0, N+1)]

direct_row = [-1, 0, 1, 0]
direct_col = [0, 1, 0, -1]

for _ in range(N):
    graph.append(list(map(int, input())))

print(graph)


def dfs(graph, visited, row, col, result):
    
    if graph[row][col] == 1 or visited[row][col] == True:
        visited[row][col] = True
        return
    visited[row][col] = True
    result.append((row, col))
    
    
	# 4방향을 살펴보고 0이면 재귀를 한다
    for d in range(4):
        new_row = row + direct_row[d]
        new_col = col + direct_col[d]
        if new_row < 0 or new_row > N-1 or new_col < 0 or new_col > M-1 or visited[new_row][new_col] == True :
            continue
        print(f'{new_row} , {new_col}')
        if graph[new_row][new_col] == 0:
            dfs(graph, visited, new_row, new_col, result)


cnt = 0   


for i in range(0, N):
    for j in range(0, M):
        result = []
        if visited[i][j] == True:
            continue
        dfs(graph, visited, i, j, result)
        if len(result) != 0:
           	# 경로가 존재한다면 result가 안의 개수가 0이 아니므로 count를 1 늘려준다
            cnt +=1

print(cnt)

 

DFS method를 좀 더 간결하게 만들어보고자 한다

• DFS method return 값을 Boolean으로 설정
• visited를 없애고 0을 방문하면 1로 바꾸는 정책으로 변경 (어차피 1은 방문할 가치가 없는 노드이기 때문)

# N - 얼음틀 세로 길이 M - 얼음틀 가로 길이
N, M = map(int, input().split())

graph = []
# visited = [[False]*(M+1) for _ in range(0, N+1)]
# visited 대신 graph의 0을 1로 바꿈으로 visited 처리

direct_row = [-1, 0, 1, 0]
direct_col = [0, 1, 0, -1]

for _ in range(N):
    graph.append(list(map(int, input())))

print(graph)


def dfs(graph, row, col):
    
    
    # 범위를 넘어선 경우
    if row < 0 or row > N-1 or col < 0 or col > M-1 :
        return False

    # 이미 방문했거나 애초부터 1인 경우
    if graph[row][col] == 1:
        return False

    if graph[row][col] == 0:
        graph[row][col] = 1
        for d in range(4):
            new_row = row + direct_row[d]
            new_col = col + direct_col[d]
            
            print(f'{new_row} , {new_col}')
            dfs(graph, new_row, new_col)
        return True



cnt = 0   


for i in range(0, N):
    for j in range(0, M):
        if dfs(graph, i, j) == True:
            cnt+=1
        



print(cnt)