[Python] 1012 - 유기농 배추

1. 문제 정의

이 문제는 MxN 크기의 리스트 내에 인접한 배추의 묶음의 갯수를 구하는 문제이다. 가로 M, 세로 N, 배추의 갯수 K가 입력으로 주어지고, 이후 K개의 좌표를 입력으로 받는다.

문제의 예시에서, 배추의 묶음은 5개 이다.

 

2. 풀이 방식

그래프의 탐색을 활용하여 문제를 해결하였다. MxN 크기의 리스트를 생성하여 배추의 위치를 저장한 후, 또 다른 리스트에 해당 위치를 방문하였는지 체크 한다. 방문한 위치에 대해 상, 하, 좌, 우에 해당하는 위치의 방문 여부를 확인. 이후 큐에 저장하여 동일한 방식으로 탐색해 나간다.

탐색을 마친 후 count를 1 증가시키고 이후의 방문을 이어나간다.

 

코드는 다음과 같다.

# 1012 유기농 배추

import sys
input = sys.stdin.readline

from collections import deque

# 다음 위치 이동을 위한
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())
    li = [[0] * M for _ in range(N)] # 배추 밭 생성성

    for _ in range(K):
        x, y = map(int, input().split())
        li[y][x] = 1 # 배추의 위치 표시시

    visited = [[0] * M for _ in range(N)] # 방문 노드 생성
    bug = 0 # 벌레의 수
    for x in range(N):
        for y in range(M):
            if (li[x][y] == 1) and (visited[x][y] == 0):
                Q = deque() # 큐 생성
                Q.append((x, y)) # 현재위치 저장장
                
                while Q: # 큐가 빌 때 까지
                    cx, cy = Q.popleft() # 큐에 저장된 위치치

                    for i in range(4): # 좌, 우, 하, 상 순서로 탐색색
                        n_x = cx + dx[i]
                        n_y = cy + dy[i]

                        if (0 <= n_x < N) and (0 <= n_y < M) and (li[n_x][n_y] == 1) and (visited[n_x][n_y] == 0): # next x, y가 배추가 심어져 있고, 방문하지 않은 위치인 경우
                            visited[n_x][n_y] = 1
                            Q.append((n_x, n_y)) # 큐에 추가하여 탐색을 이어 나간다.

                bug += 1

    print(bug)

 

3. 후기

탐색 문제를 해결하기 위해선 조건이 중요하다는 것을 깨달았다.

for문을 이용하여 탐색을 할 때, x와 y는 무조건 증가하니 탐색 방향이 무조건 앞쪽이다. 따라서 next 점은 무조건 오른쪽, 아래쪽이라 생각하여 문제를 해결하려 하였으나, 생각처럼 되지 않았고 상, 하, 좌, 우 모두를 조건에 추가해주니 문제가 해결되었다. 조건에 대해 더 신중히 생각하게 된 계기가 되었다.