[이취코-PART2-DFS/BFS] 음료수 얼려먹기

문제

부스트캠프 코딩테스트를 보고.. 구현 뿐만 아니라 이 외의 유형들도 많이 풀어보자고 다짐을 해서 1주일에 최소 4문제는 풀어볼까 한다.

그래서 오늘 처음으로 DFS와 BFS를 공부하기 시작했고 그 첫 문제가 이 문제였다.
역시나 푸는데 너무 어려워서 다른 분의 풀이를 참고했다.

풀이

일단 이 문제를 보고 DFS로 풀어야 하나 BFS로 풀어야 하나 고민을 많이했다가.. 결국 DFS로 풀기로 결정했다. DFS로 결정한 이유는 1을 만나게 되면 탐색을 중단해야 하기 때문에? 뭔가 DFS가 더 적당해보였다.
확실한 이유는 아니다..ㅎㅎ

그래서 각 좌표들마다 직접 구현한 dfs 함수를 적용시켜서 True가 반환되면 1개씩 증가하는 식으로 로직을 구현했다.

"""
이취코 DFS/BFS PART2: 음료수 얼려먹기
난이도: 1.5 / 3
"""

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

def dfs(x, y):
    if x < 0 or y < 0 or x >= n or y >= m:   # 좌표 넘어가면 함수 종료
        return False

    if ice[x][y] == 0:
        ice[x][y] = 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False



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

print(count)

x또는 y좌표가 얼음틀 좌표를 넘어가면 False를 반환시켜서 탐색을 종료시켜야 한다.
그리고 현재 좌표가 0이면 추가 탐색이 가능하기 때문에 상하좌우 탐색을 재귀함수를 통해 진행시킨다.
그래서 탐색이 다 끝나면 True를 반환시키면 된다.

후기

이거 풀때는 이렇게 구현해야겠다는 생각을 전혀 못했고, DFS와 BFS라는걸 느낌을 잡는데 아직은 좀 많이 어려운 것 같다.
이 유형들의 문제를 자주 풀어보면서 더욱 감을 익혀야 할 것 같다!