문제

배추 밭에 배추를 키우기 위해선 해충 방지를 위해 지렁이를 배치한다. 지렁이는 배추 서로 인접해서 붙어있는 곳들은 1마리로 충분하다. 이때 배추밭의 크기와 배추의 위치가 주어질 때 필요한 지렁이의 숫자를 출력해주면 된다.

코드

tc = int(input())

for i in range(tc):
    col, row, cabageCount = map(int, input().split())
    cabageLocation = dict()
    stack = list()

    for j in range(cabageCount):
        x, y = map(int, input().split())
        cabageLocation[(x, y)] = False
    warm = 0
    for a, b in cabageLocation:
        if not cabageLocation[(a, b)]:
            stack.append((a, b))
            while len(stack) != 0:
                e, f = stack[-1]
                cabageLocation[(e, f)] = True
                if (e + 1, f) in cabageLocation and not cabageLocation[(e + 1, f)]:

                    stack.append((e + 1, f))
                elif (e - 1, f) in cabageLocation and not cabageLocation[(e - 1, f)]:
                    stack.append((e - 1, f))
                elif (e, f + 1) in cabageLocation and not cabageLocation[(e, f + 1)]:
                    stack.append((e, f + 1))
                elif (e, f - 1) in cabageLocation and not cabageLocation[(e, f - 1)]:

                    stack.append((e, f - 1))
                else:
                    stack.pop()

            warm += 1
    print(warm)

설명

나는 배추 밭(2차원 배열)을 따로 만들지 않고 주어진 배추들의 위치를 저장한 후에 처음 배추의 위치를 스택에 저장하고 그 위치에 상, 하, 좌, 우의 위치에 배추가 있는지 배추 위치가 저장된 리스트에서 찾는다. 있다면 방문 표시(True)를 해주고 계속 탐색한다음에 더이상 존재하지 않으면 pop을 해주는 방식으로 풀었다.