[이코테] DFS - 음료수 얼려 먹기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

N by M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분까지 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하라.

입력조건

• 첫 번째 줄에 얼음 틀의 세로길이 N과 가로길이 M이 주어진다.(1 <= N, M <= 1,000)
• 두 번째 줄부터 N+1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력조건

• 한 번에 만들 수있는 아이스크림의 개수를 출력한다.

사고과정

• 풀이 아이디어에 대한 감이 하나도 안떠올랐다. 그냥 머릿속에 맴도는 것은 DFS는 스택, 재귀함수를 이용해야 해. 끝...
• 너무 답답해서 풀이를 보았다. 아이디어는 어쨌거나 Array의 한 인덱스 씩 모두 상,하,좌,우를 탐색하는 것이었다. 그런데 상,하,좌,우를 탐색할 때 재귀함수를 사용했다는 것..
• 그래프 형태로 모델링 하면 아이디어가 떠오른다는데 아직 난 그단계가 아닌 듯하다..
• 핵심 아이디어는 특정한 지점의 상,하,좌,우 주변은 재귀적으로 탐색하면서 값이 0이면서 아직 방문하지 않은 지점이라면 해당 지점을 방문. 그래서 방문하는 처리 로직이 추가로 필요함
• 사실 직관적으로 이해가 잘 가진 않음.. 계속 반복해서 풀어야 할 듯 함

풀이

import sys

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


def dfs(x, y):
    # 좌우탐색한 좌표들이 범위 벗어날 때 False
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    # 좌우탐색 시작
    if graph[x][y] == 0:
        graph[x][y] = 1  # 방문처리
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True   # True가 반환된다는 것 = DFS 완료되었다는 것
    return False  # 칸막이(1)에 부닥쳤을 때


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