[Ch.5 - DFS/BFS] 음료수 얼려 먹기

My code

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

went = [[0] * m for _ in range(n)]

ice = []
for i in range(n):
    ice.append(list(map(int,input().split())))

def dfs(x,y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if ice[x][y] == 0 and went[x][y] == 0:
        went[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) == True:
            result += 1

print(result)

Answer

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

graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

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) == True:
            result += 1

print(result)

Code Review

이번 문제는 DFS 를 이용하여 탐색 문제를 해결하는 것이었습니다. 아이스크림의 총 개수를 알아내기 위해서 상, 하, 좌, 우로 서로 인접한 0을 모두 찾아주어야 합니다. 따라서 얼음 틀을 저장할 2차원 리스트와 방문했음을 표시할 맵을 만들어주었습니다. 만약 얼음 틀의 범위를 벗어나면 False 를 return 하도록 해주었고 방문 값과 얼음 틀 값이 모두 0이라면 방문 값을 1로 설정해주고 재귀함수를 이용하여 해당 위치의 상, 하, 좌, 우의 값을 탐색할 수 있도록 해주었습니다. 재귀함수는 return 을 할 때 호출 되었던 위치로 다시 돌아갑니다. 따라서 모든 위치에서의 상, 하, 좌, 우를 모두 탐색할 수 있습니다. 탐색이 끝나면 True 를 return 해주어 아이스크림 한 개의 개수를 세어줍니다.  
Answer code 는 방문 위치를 저장해주지 않고 얼음 틀의 값을 직접 1로 바꾸어 더 간단하게 구현되었습니다.