과정 정리

• 안올리려다가 구현이 생각보다 복잡했어서 생각 정리할겸 블로그에 정리한다.
• 문제에서 예제 출력만 꼭 정답이 아니라고 했으니 겹쳐있을 수 있는 모든 십자가 중 가장 큰 십자가를 찾아서 세어주는 과정을 반복해야 한다.
  - 여기서 첫번째 실수 : 정답이 여러개라는 설명을 무시했음.
  
• 가장 큰 십자가를 찾고 해당하는 위치의 좌표값과 크기를 리스트에 넣어준 뒤 출력해주었음
  - 이때 예제 3과 같은 모형일 때 반례가 발생함
  • 그래프탐색과 마찬가지로 visited를 만들어주어 비교하는 방법을 쓰는건 어떨까라고 생각만 함..
    결국엔 그 방법으로 풀음
• 보니까 마지막에 정렬을 해뒀는데 사실 맨 처음 방법으로 풀 때 출력예시와 동일한 결과를 내야 하는 줄 알고 그랬는데 굳이 필요없는 과정이고, 그냥 출력하면 됨

코드 설명

• 주어진 그래프와, 그 그래프를 deepcopy한 copied 그래프를 하나 만든다

• 그래프를 돌면서, 각각의 인덱스에 대한 십자가의 사이즈를 찾는 함수 find에 넣고 돌린다.
  - find 함수 내부에서 십자가가 포함된다면 1이상의 사이즈를 리턴하며, 그렇지 않다면 0을 리턴한다. 이때 주의할 점은 십자가를 찾을 때 다음 인덱스가 범위를 벗어나지 않도록 예외처리가 필요하다.

• 리턴된 사이즈를 가지고, 복사된 그래프에 십자가를 지운다.

• 복사된 그래프를 1차원으로 변환 후 * 이 남아있다면 십자가는 존재하지만 모든 별을 제거하지 못한 경우이고, result가 0이라면 십자가를 제거할 수 없었다는 뜻이다.

• 이후 result 결과를 출력한다.
  

from copy import deepcopy
n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
copied = deepcopy(graph)

def find(x, y):
    size = 0
    if graph[x][y] != '*':
        return 0

    flag = True
    while flag:
        size += 1
        dx, dy = [1 * size, -1 * size, 0, 0], [0, 0, 1 * size, -1 * size]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '*':
                continue
            else:
                flag = False
                break
    return size

result = []
for i in range(n):
    for j in range(m):
        size = find(i, j)
        if not size:
            continue
        
        if size - 1 != 0:
            result.append([i+1, j+1, size-1])

            for a in range(size):
                dx, dy = [1 * a, -1 * a, 0, 0], [0, 0, 1 * a, -1 * a]
                for b in range(4):
                    nx, ny = i + dx[b], j + dy[b]
                    copied[nx][ny] = '.'

if result == [] or '*' in sum(copied, []):
    print(-1)
    exit()

print(len(result))
for r in sorted(result, key= lambda x:(x[0], x[1], -x[2])):
    print(*r)