[이코테] 음료수 얼려 먹기 (DFS).py

▶ 입력 예시

4 5

00110

00011

11111

00000

 

▶  출력 예시

: 3

 

Code

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

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

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i,j) == True:
            result += 1
            
print(result) # 정답 출력

실행 결과

 

▶  배운점

: 먼저 현재 위치에서 DFS를 수행한다.

DFS 함수로 들어가, 초기 조건으로 지정 범위를 벗어날 경우 종료한다.

현재 노드를 방문하지 않았다면 graph[x][y] ==0   방문처리를 한다. graph[x][y] ==1

여기서 4방향의 이동경로를 모두 재귀호출을 한다. 그럴경우 방문하지 않은 '0'을 모두 돌게 되고,

그 상태일 때 DFS를 나와 result가 +1이 된다. 이게 하나의 집단(아이스크림)이 카운트된 것이다.

2중 for문으로 모든 경우의 수를 반복하고, 최종적으로 3개의 집단이 카운트된다.

 

알고리즘 풀이를 통해 DFS가 동작하는 순서와 원리를 이해할 수 있었다.

방문하지 않은 노드를 찾아 하나씩 땅따먹기 하는.. 그런 게임처럼 보인다.

이 구성을 코드로 직접 짤 수 있을만큼 반복적으로 연습함이 필요하다.

 

 

문제 출처:  42분43초

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3