백준 1012

백준 1012번 - 유기농 배추

 제목대로 배추를 유기농으로 키우기 위해 배추흰지렁이를 얼마나 구입해야 하는 가를 구하는 것으로 2차원 크기의 공간에 배추를 심었을 때 인접한 배추끼리는 지렁이가 이동할 수 있어 인접한 배추끼리는 지렁이 1마리만 필요하고 지렁이 개수를 구하는 문제이다. 평소엔 프로그래머스 코테 연습 문제를 풀다가 백준이 문제도 더 많고 더 세분화된 단계로 나눠져 있는 등 잘되어 있는거 같아서 심심해서 풀었다.

입력

• 입력 첫 줄에 테스트 케이스의 개수
• 두번째 줄은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)
• 3번째 줄 이후 부턴 배추의 위치를 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)로 표현

출력

• 각 테스트 케이스에 대한 최소 배추흰지렁이 마리 수

예제 입력, 출력

• 예제1

  # 입력                                           # 출력
  2                                                5
  10 8 17                                          1
  0 0
  1 0
  1 1
  4 2
  4 3
  4 5
  2 4
  3 4
  7 4
  8 4
  9 4
  7 5
  8 5
  9 5
  7 6
  8 6
  9 6
  10 10 1
  5 5
  

• 예제 2

  # 입력                                          # 출력
  1                                               2
  5 3 6
  0 2
  1 2
  2 2
  3 2
  4 2
  4 0
  

접근법

 우선 배추가 1개일 경우 지렁이는 1마리만 필요하기 때문에 아래 조건을 추가했다.

    if napacabbage == 1:
            print("1")
            continue

근접한 배추들을 모두 찾기 위해선 하나를 발견하면 또 하나를 발견하고 또 발견하는 식으로 가야하기 때문에 재귀 함수를 써야겠다고 생각했다.

• 먼저 좌표가 담긴 리스트를 복사하여 원본 xy리스트와 복제본 xy리스트를 만들었다.

  xy_list_dup = xy_list.copy()
  

• 재귀 함수에서 입력받은 x,y의 위치에서 인접한 배추를 찾아내어 복제 xy리스트에서 해당 좌표를 삭제하고 다시 재귀함수를 호출하는 형식으로 함수를 만들었다.

  def check_close(x,y):
    global xy_list_dup
    if [x,y-1] in xy_list_dup:
        xy_list_dup.remove([x,y-1])
        check_close(x,y-1)
    if [x,y+1] in xy_list_dup:
        xy_list_dup.remove([x,y+1])
        check_close(x,y+1)
    if [x-1,y] in xy_list_dup:
        xy_list_dup.remove([x-1,y])
        check_close(x-1,y)
    if [x+1,y] in xy_list_dup:
        xy_list_dup.remove([x+1,y])
        check_close(x+1,y)
  

• 또한 for 문이 돌 때 재귀 함수로 인해 복제 xy리스트가 삭제 됐는지를 조건문을 추가해 판별하여 삭제된 x,y 좌표들을 하나로 묶는다는 개념으로 count+=1를 해주었다.

  for x, y in xy_list:
    xy_list_dup_len = len(xy_list_dup)
    check_close(x,y)
    # 재귀함수 호출 전화 후를 비교하여 바뀌었는지 검사
    if xy_list_dup_len != len(xy_list_dup):
        count +=1
  

• 마지막으로 인접한 배추가 없는 혼자 따로 떨어져 있는 배추 들은 복제 xy리스트에 남아 있으므로 len(xy_list_dup)+count를 출력하게 해주었다.

  print(len(xy_list_dup)+count)
  

전체 코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())

#가까운 배추가 있는지 찾는 재귀함수
def check_close(x,y):
    global xy_list_dup
    if [x,y-1] in xy_list_dup:
        xy_list_dup.remove([x,y-1])
        check_close(x,y-1)
    if [x,y+1] in xy_list_dup:
        xy_list_dup.remove([x,y+1])
        check_close(x,y+1)
    if [x-1,y] in xy_list_dup:
        xy_list_dup.remove([x-1,y])
        check_close(x-1,y)
    if [x+1,y] in xy_list_dup:
        xy_list_dup.remove([x+1,y])
        check_close(x+1,y)

#전체 실행 회수
for _ in range(n):
    xy_list=[]

    # 입력받기
    x_total, y_total, napacabbage = map(int, input().split())
       
    for _ in range(napacabbage):
        xy_list.append(list(map(int, input().split())))
    
    # 배추가 1개일 경우
    if napacabbage == 1:
        print("1")
        continue
    
    count=0
    xy_list_dup = xy_list.copy()
    for x, y in xy_list:
        xy_list_dup_len = len(xy_list_dup)
        check_close(x,y)
        # 재귀함수 호출 전화 후를 비교하여 바뀌었는지 검사
        if xy_list_dup_len != len(xy_list_dup):
            count +=1
    print(len(xy_list_dup)+count)