[백준 1012] 유기농 배추(python)

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

유기농 배추 문제

인접해있는 칸들로 이루어진 영역이 총 몇개인지 구하는 문제

BFS나 DFS를 이용하면 쉽게 풀 수 있는 문제

 

내가 푼 정답코드

def warm(a,b):
    visited = [[0]*M for _ in range(N)]
    queue = [[a,b]]
    visited[a][b] = 1
    cnt = 0
    while queue:
        cnt += 1
        y, x = queue.pop(0)
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == 0 and cabbage[ny][nx] != 0:
                visited[ny][nx] = visited[y][x] + 1
                cabbage[ny][nx] = 0 #이후 이어있는 배추 수 안세기 위해 없애주자
                queue.append([ny,nx])
    return cnt


import sys
T = int(sys.stdin.readline())
for case in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    cabbage = [[0]*M for _ in range(N)]
    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())
        cabbage[b][a] = 1
    move = [[1,0],[-1,0],[0,1],[0,-1]]
    result = [] # 벌레 마리 수
    for i in range(N):
        for j in range(M):
            if cabbage[i][j] == 1:
                result.append(warm(i,j)) # 해당 지역수를 result에 추가
    print(len(result))

BFS를 활용하여 풀어주었고, 위 코드처럼 도착 지점까지의 거리를 구하는 식의 코드를 사용할 필요는 없지만, 가장 중요한 부분은 이동 할 수 있는 다음 영역을 0으로 초기화 해주는것이다. 그래야 for문을 통해 탐색하면서 다시 같은 영역을 재 탐색하는 일이 없어지기 때문이고, 영역 표시 해주기 위해서 영역 갯수를 cnt로 표시해주었다.

사실 cnt로 할 필요 없이 그냥 위 bfs를 돌리면 처음 만난 1인 지역을 제외하고 전부 0으로 만들기 때문에, 그냥 BFS 이후에 cabbage 내에 있는 1의 갯수를 세도 동일하게 출력 할 수 있을 것이다.

---

느낀 점

DFS 혹은 BFS를 이용하여 해결 할 수 있는 문제를 연습 중에 풀게된 문제. DFS나 BFS 개념을 알고 있다면 쉽게 접근할 수 있지만, 보통 미로 찾는 문제만 해결했지, 이렇게 떨어진 영역 칸 수의 갯수를 찾는 문제는 처음 접해봐서 접근법을 조금 생각해봐야 했단게 좋은 문제였던거 같다.