음료수 얼리기

끝까지 내 힘으로 문제를 풀어내서 너무 뿌듯해!

🎯 음료수를 얼려먹는 문제인데 칸막이를 잘 생각해서 어디가 어는지 파악해야 하는 문제!

📌 input data 2차원 list로 처리한다음 graph로 탐색하면 되겠다.
📌 상하좌우 이동해보고 0인지를 체크하고 0이면 'X'표시 해줘야지

shallow copy를 그냥 이용했다. 원본 data를 다시 쓸 일이 없기 때문에..

1. loop를 돌리면서 0이면 탐색을 시작했다.
2. stack을 이용한 DFS로 풀었는데 queue를 이용한 BFS도 똑같이 풀 수 있다! 우선 stack에 append한 후 스택이 빌 때까지 loop를 돌려준다.
3. loop를 도는 동안 next row, col이 vaild한지를 체크하면 끝!

# 아직도 음료수를 왜 이런 케이스로 얼려먹는지 모르겠다.

import sys
sys.stdin = open('test.txt', 'r')

n, m = map(int, input().split())
card = []

def isvalid(graph, data, row, col):
    if row < 0 or row >= n:
        return False
    if col < 0 or col >= m:
        return False
    if graph[row][col] != data:
        return False
    return True

def check_bfs(graph, row, col):
    stack = [(row, col)]
    data = graph[row][col]
    graph[row][col] = 'X'

    dr = [1, -1, 0, 0]
    dc = [0, 0, -1, 1]
    while stack:
        row, col = stack.pop()
        for i in range(4):
            next_r = row + dr[i]
            next_c = col + dc[i]
            if isvalid(graph, data, next_r, next_c):
                stack.append((next_r, next_c))
                graph[next_r][next_c] = 'X'

for _ in range(n):
    card.append(list(map(int, list(input()))))

cnt = 0
for i in range(n):
    for j in range(m):
        if card[i][j] == 0:
            check_bfs(card, i, j)
            cnt += 1

print(cnt)