[백준/파이썬] 1012번 유기농 배추 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1012번 유기농 배추
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

각 테스트 케이스에 대해 인접그룹으로 묶을 수 있는 배추 그룹 수를 출력

코드

for _ in range(int(input())):
    m, n, k = tuple(map(int, input().split()))
    bae = [[0]*n for _ in range(m)]
    for _ in range(k):
        x, y = tuple(map(int, input().split()))
        bae[x][y] = 1

    while(max(map(max, bae)) > 0):
        cnt = 0
        stack = list()
        for i in range(m):
            for j in range(n):
                if(bae[i][j] == 1):
                    cnt +=1
                    stack.append((i, j))
                    while(len(stack) > 0):
                        x, y = stack.pop()
                        if(x+1 < len(bae) and bae[x+1][y] == 1): stack.append((x+1, y))
                        if(y+1 < len(bae[x]) and bae[x][y+1] == 1): stack.append((x, y+1))
                        if(x > 0 and bae[x-1][y] == 1): stack.append((x-1, y))
                        if(y > 0 and bae[x][y-1] == 1): stack.append((x, y-1))
                        bae[x][y] = 0
                        continue
    print(cnt)

설명

각 테스트 케이스에 대해 m,n,k를 먼저 입력받습니다.

이후, 배추의 정보를 저장할 bae 변수를 선언해 n행 m열의 리스트를 생성합니다.

파이썬은 비록 array가 아니라 list지만, 리스트를 행우선으로 구현합니다.

하지만 이번에는 좌표를 xy 좌표계로 나타내기 용이하기 위해 [[0]*n for _ in range(m)]로 선언합니다.

왜냐하면, x는 가로축을 나타내는 좌표이므로, 열에 매칭시켜야되죠.

하지만, 행렬은 보통 행을 우선으로 표현합니다. 이번에는 열을 우선으로 표현하기 위해 위와같이 선언한 것입니다.

이후, 각 칸을 순회하며 처음 배추가 발견된 지점에서 완전탐색을 실시합니다.

이 완전탐색은 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search) 아무거나 상관없습니다.

심지어 저 두개가 아니라 독자적인 규칙을 만들었다고 해도 상관없습니다. 그냥 인접한 배추만 다 묶을 수 있으면 상관없어요

하지만, 여기서는 깊이 우선 탐색으로 구현합니다.

DFS를 하기 위한 스택을 선언하고, 처음 배추가 발견된 좌표에서 탐색을 실시, 탐색이 끝나면 다시 좌표계를 순회합니다.

탐색과정에서 방문한 배추는 0으로 표시해서 다시 방문하지 않도록 합니다.

이 동작을 모든 배추가 0이 될때까지 합니다. 이 때, 반복횟수가 바로 이웃한 배추 그룹의 수입니다.

즉, 배추 그룹 수 만큼 지렁이가 필요하므로 반복 횟수를 출력하면 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---