[백준] 16924번: 십자가 찾기 - Python

링크: https://www.acmicpc.net/problem/16924

 

아이디어

• *로 십자가를 만드는게 요지가 아니였음
• 십자가로 입력된 격자를 완성 할 수 있냐 없냐가 주 요구사항이다
• 십자가로 만든 격자를 표시해야 할 리스트 하나를 만들고 가자
  • * 위치를 1로 지정하고 나머지를 0으로 해두자
• 이제 * 위치를 기준으로 만들 수 있는 십자가를 탐색하고 표시용 리스트애 표시하자
  • size크기로 중간 기준 상 하 좌 우 좌표의 값이 유효한 위치인지 또한 *이 맞는지 판별
  • 아니라면 바로  return으로 함수 종료
  • 십자가가 완료됐다면
  • 십자가의 중심 좌표를 저장
  • 그 십자가 영역의 좌표를 표시 리스트에 표시 (1->0)
  • size를 키워가며 모두 탐색
• check 리스트를 판단하고 모든 영역이 채워지지 않았으면 -1 출력 후 종료
• 무두 채워졌으면 정렬을 진행
  • y, x에 대해 오름차순 크기에 대해 내림차순이라 lambda 이용하여 정렬

구현

import sys
input = sys.stdin.readline

# 음 그냥 모든 점에서 십자가가 되는지 안되는지 판단해야할듯?
# 근데 출력 순서가 안나와있네
# 아 *로 십자가를 만들 수 있냐 없냐가 요지가 아니였네
# 십자가로 입력 리스트의 *을 다 만들 수 있는지 보는거였넹
N, M = map(int, input().split())

li = [list(input().strip()) for _ in range(N)]
check = [[0]*M for _ in range(N)]

# 십자가 판별
def cross(y, x):
    size = 1
    while 1:
        for dy, dx in [(0,size), (size,0), (0,-size), (-size,0)]:
            ny = y + dy
            nx = x + dx
            if not(0 <= ny < N and 0 <= nx < M) or li[ny][nx] != '*':
                return
            
        stars.append((y+1,x+1,size))
        # 십자가 완성된 영역 표시
        check[y][x] = 0
        for dy, dx in [(0,size), (size,0), (0,-size), (-size,0)]:
            ny = y + dy
            nx = x + dx
            check[ny][nx] = 0

        size+=1


stars = []

# 십자가로 완료해야할 영역 표시
for i in range(N):
    for j in range(M):
        if li[i][j] == '*':
            check[i][j] = 1
# * 기준 십자가 판별 함수 호출
for i in range(N):
    for j in range(M):
        if li[i][j] == '*':
            cross(i, j)

# 십자가로 못만든 영역 확인
for i in check:
    if sum(i) != 0:
        print(-1)
        exit()

stars.sort(key=lambda x: (x[0], x[1], -x[2]))
print(len(stars))
for star in stars:
    print(*star)

 

 

마무리

문제가 그냥 *로 십자가를 만들 수 있는 경우를 구하는걸로 넘겨집고 풀었었다.

당연히 그럴줄 알았다.. 근데 완전 다른 요구사항의 문제였다. 문제를 잘 읽고 풀어야지 인지하고 있었는데 내가 맘대로 생각해서 시간 날린 문제.. 

하지만 요지를 파악하자마자 한번에 성공~~!