[Python : 나동빈] 음료수 얼려 먹기

문제

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

• N * M 행렬을 입력 받는다.
• 행렬상의 0은 음료얼음, 1은 플라스틱
• 0이 이어지면 한 덩어리로 취급한다.
• 음료얼음 덩어리는 총 몇 개인가?

# 입력 예시
4 5
00110 
00011
11111
00000

# 출력 예시
3

풀이

DFS로 푸는게 적합해 보였다.

• 0과 1로 이루어진 행렬을 x,y 좌표로 하나씩 훑어나간다.
• 만일 x, y 좌표가 0보다 작거나 N,M보다 크다면 False 반환한다.
• 0을 만나면 1로 바꾼후, 상하좌우 DFS를 재귀시키고 True를 반환한다.
• 1을 만나면 바로 False를 반환한다.
• 가장 먼저 재귀를 동작시킨 곳에서 True를 반환 받으면, 얼음덩어리 1개를 찾은 것이다.

def dfs(juice, x, y, N, M):
    if x < 0 or x >= N or y < 0 or y >= M:
        return False

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

def solution():
    ice = 0
    N, M = map(int, input().split())
    juice = []

    for i in range(N):
        juice.append(list(map(int, input())))

    for x in range(N):
        for y in range(M):
            if dfs(juice, x, y, N, M): ice+= 1

    print(ice)

solution()

프로그래머스에서 풀듯이 solution 함수로 묶어서 해봤다.