백준 알고리즘 1012 (유기농 배추) - python (재풀이)

백준 알고리즘 1012 (유기농 배추) - python

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

1012번: 유기농 배추

 

다시 코딩 연습을 시작한다! 가즈아!!!

거의 백지인 상태지만(ㅠ) 이전에 풀었던 문제들을 다시 재풀이해본다.

 

위 문제를 요약하면, Map의 크기와 1의 좌표 위치를 받아서

1의 군집이 몇 개 있는지를 체크하는 문제이다.

 

[문제 풀이]

1. 입력들을 받아서 _map에 저장

2. 처리할 수 있는 간단한 예외는 미리 처리 (0, 1, 전체) -> 처리 속도 향상

3. BFS의 시작 좌표를 체크하면서

4. BFS 함수 내에서 1을 계속 따라간다.

5. 더이상 따라갈 수 없으면 따라간 길이를 가지고 return

6. BFS 함수에서 받은 값들(1의 군집들)을 result에 저장

7. result의 length를 출력

 

[Code]

import sys
sys.setrecursionlimit(10**4)

def BFS(depth, sy, sx):  # depth, start y, start x
    # 상하좌우 이동
    dy = [-1, 0, 1, 0]  # delta y
    dx = [0, 1, 0, -1]  # delta x
    for i in range(4):
        ny, nx = sy + dy[i], sx + dx[i]  # next x, next y
        if  0 <= ny < N and 0 <= nx < M:
            # 상하좌우 중 map 값이 1이고, 체크 안했을 경우
            if _map[ny][nx] and not visited[ny][nx]:
                visited[ny][nx] = True  # 체크
                BFS(depth+1, ny, nx)  # 계속 더 가본다
    # 더이상 못 가면 depth 출력
    return depth

if __name__ == '__main__':
    T = int(sys.stdin.readline())
    for _ in range(T):
        # 가로, 세로, 1의 갯수
        M, N, K = map(int, sys.stdin.readline().split())
        _map = [[0] * M for _ in range(N)]  # map
        visited = [[False] * M for _ in range(N)]  # 방문 체크
        result = []  # 1을 따라 끝까지 가 본 갯수 결과 저장
        for _ in range(K):  # 1의 좌표 수집
            # x는 M에 대응, y는 N에 대응
            _x, _y = map(int, sys.stdin.readline().split())
            _map[_y][_x] = 1
        # 간단한 예외 상황 처리
        if K == 0:
            print(0)
            continue
        elif K == 1 or K >= M * N - 1:
            print(1)
            continue
        for y in range(N):
            for x in range(M):
                # 체크 안 한 1을 최초 발견하면
                if _map[y][x] and not visited[y][x]:
                    visited[y][x] = True
                    # 거기부터 쭉 따라가본다
                    result.append(BFS(0, y, x))
        print(len(result))  # 군집의 갯수 출력