[알고리즘] 음료수 얼려 먹기

문제 링크

킹빈나 이코테 강의(DFS & BFS)

문제 정의

문제 풀이

일단 양옆 위아래로 벽을 씌운다.
00110
00011
11111
00000 을

1111111
1001101
1000111
1111111
1000001
1111111 로 바꾼다.

다음 (1,1)지점부터 상하좌우를 살피고 이 곳을 방문했다는 표시를 남긴다.

상하좌우 중 0이 있으면 또 상하좌우를 살피고 방문 표시를 남긴다. (반복)

한번의 사이클이 다 돌면(더 이상 0이 없을때), 답을 1 증가 시킨다.

(1,2) (1,3) (1,4)... 이렇게 탐색.(방문하지 않은 곳만)

내 코드

import sys


def find(myArr, i, j):
    if myArr[i][j] != 0:
        return
    else:
        myArr[i][j] = 2
        find(myArr, i-1, j)
        find(myArr, i, j+1)
        find(myArr, i+1, j)
        find(myArr, i, j-1)

N, M = map(int, sys.stdin.readline().split())

myArr = []

wall = [1]*(M+2)
myArr.append(wall)

for i in range(N):
    row = [1]
    temp = list(map(int, input()))
    for j in range(M):
        row.append(temp[j])
    row.append(1)

    myArr.append(row)

myArr.append(wall)

ans = 0

for i in range(1, N+1, 1):
    for j in range(1, M+1, 1):
        if myArr[i][j]==0:
            find(myArr, i, j)
            ans += 1

print(ans)