[DFS] -음료수 얼려 먹기

N x M  크기의 얼음 틀이 있다.

0은 구멍이 뚫려있는 부분, 1은 칸막이가 존재하는 부분이다.

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

 이때 연결된 한 덩어리를 아이스크림 1개라고 할때 몇개의 아이스크림이 생성 되는가?

 

입력 예시)

4 5

00110

00011

11111

00000

 

출력 예시)

3

 

나의 코드

def DFS(x,y,arr):
    arr[x][y]=1
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<n and 0<=ny<m and arr[nx][ny]==0:
            DFS(nx,ny,arr)


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

arr=[list(map(int,input())) for _ in range(n)]
cnt=0

for i in range(n):
    for j in range(m):
        if arr[i][j]==0:
            
            cnt+=1
            DFS(i,j,arr)



print(cnt)

전형적인 완전탐색 DFS문제이다.

처음 이중반복문으로 모든 좌표를 탐색하기 시작하여 0을 발견하면 cnt를 하나 증가하고  DFS를 호출한다.

DFS에서는 상하좌우로 완전 탐색을 시작하며 0을 만날 때마다 1로 변경하며 이미 탐색을 끝났음을 체크한다.

그리고 DFS는 모든 탐색(0을 모두 1로 변경)이 끝나면  다시 이중 반복문으로 돌아간다.

그리고 위 과정을 반복하며 연결된 영역들을 카운팅한다.

 

정답 코드

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) # 정답 출력

 

흠... 역시 이코테 책의 풀이는 오히려 이해를 방해하는 코드 같다..

내가 짠 코드가 훨씬 간결하고 좋은 코드 같다..!