[백준 알고리즘: python 3] #1012 - 유기농 배추

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

 

1012번은 구역 나누기 같은 문제입니다. 문제에서 주어지는 예제에서는 아래와 같은 상황이 주어졌고,

예제의 지렁이 구역

문제의 규칙에 따라 지렁이는 배추가 있는 위의 그림에 빨간색 동그라미로 감싸져 있는 인접한 1들의 모임입니다. 즉, 배추의 구역들을 나누는 문제입니다. 문제에서는 지렁이가 상하좌우만 움직일 수 있기 때문에 우리가 찾아야 하는 인접한 배추들이라 하면 상하좌우 4방의 배추만 인접하다고 할 수 있겠군요.

 

 

Hint!

저는 배추가 있는 곳의 좌표의 인접한 구역에 배추가 있는지 모두 확인하여 영역을 구별지었습니다. 그래서 M과 N과 같은 배추밭의 크기와 관련된 input은 사용되지 않았습니다. 제가 풀어낸 순서에 대해 간단히 정리해 볼게요!:

 

1. 각 케이스마다 input으로 받아지는 모든 좌표를 [x, y]의 형태로 coords 라는 리스트에 모두 append 합니다.
2. coords에 좌표가 남아 있는 동안 아래의 과정을 거칩니다. 이 때, 결과값(group_num)은 0으로 먼저 할당해 둡니다.
   1. group_num에 1을 더하고, coords의 첫번째 값을 pop(coords의 첫번째 값을 반환함과 동시에 coords에서 그 값는 삭제 됩니다.)하여 current_coord에 저장합니다.
   2. neighbors 리스트를 [current_coord]로 선언을 한 뒤, neighbors에 좌표가 존재한다면 아래의 과정을 거칩니다.
      1. neighbors 리스트에 있는 좌표 각각에 대하여 인접한 좌표의 후보를 구하고,
      2. 각 후보들이 coords에 존재하면 이를 더미 리스트(temp)에 넣어주고, coords에서는 그 좌표를 삭제합니다.
      3. neighbors를 temp로 초기화시킵니다.(temp에 있는 좌표들과 인접한 좌표가 있는지 다시 탐색.)

굵은 글씨로 쓰여져 있는 부분은 coords의 요소들을 소모하고 있는 부분을 의미합니다. coords에서 탐색을 실행한 좌표와 탐색된 좌표를 삭제하는 과정을 통해 이미 탐색된 좌표는 다시 재탐색이 되지 않도록 할 수 있어서 코드를 짜기가 편리했습니다. 모든 좌표들을 소모하게 되면 알고리즘이 종료되고, 그 동안 그룹이 몇 개가 생성되었는지를 결과로 보여주면 됩니다!

 

이렇게 해서! 아래의 코드로 성공하였습니다.

 

import sys

T = int(sys.stdin.readline())
results = []

for _ in range(T):
	# 이 코드에서 M과 N은 사용되지 않습니다.
    M, N, K = map(int, sys.stdin.readline().split())
    coords = []
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        coords.append([x, y])

	# groups 딕셔너리와 관련된 코드는 사실 없어도 되지만, 처음 코드를 짤 때 디버깅 용도로 만들어 두었습니다.
    # 각 그룹마다 포함된 좌표들을 정리해두는 딕셔너리 입니다.
    groups = {}
    group_num = 0
    while coords:
        group_num += 1
        current_coord = coords.pop(0)
        groups[group_num] = [current_coord]
        neighbors = [current_coord]
        while neighbors:
            temp = []
            for neighbor in neighbors:
                x = neighbor[0]
                y = neighbor[1]
                # 인접한 배추의 좌표들(후보)
                neighbor_candidates = [[x+1, y], [x, y+1], [x-1, y], [x, y-1]]
                for neighbor_candidate in neighbor_candidates:
                    if neighbor_candidate in coords:
                        coords.remove(neighbor_candidate)
                        temp.append(neighbor_candidate)
            neighbors = temp
            groups[group_num] += neighbors
    results.append(group_num)

for result in results:
    sys.stdout.write(str(result)+'\n')