[Python] 백준 16924번 (십자가 찾기)

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다.

아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

              ...*...
      ..*..   ...*...
.*.   ..*..   ...*...
***   *****   *******
.*.   ..*..   ...*...
      ..*..   ...*...
              ...*...

크기가 N×M이고, '.'과 '*'로 이루어진 격자판이 주어진다. 이때, 십자가만을 이용해서 격자판과 같은 모양을 만들 수 있는지 구해보자. 십자가는 서로 겹쳐도 된다. 사용할 수 있는 십자가의 개수는 N×M이하이어야 한다. 격자판의 행은 위에서부터 1번, 열은 왼쪽에서부터 1번으로 번호가 매겨져 있다.

입력

첫째 줄에 격자판의 크기 N, M (3 ≤ N, M ≤ 100)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다.

출력

십자가만 이용해서 입력으로 주어진 격자판을 만들 수 없으면 -1을 출력한다.

만들 수 있는 경우에는 필요한 십자가의 수 k(0 ≤ k ≤ N×M)를 출력한다. 다음 k개의 줄에는 그려야 하는 십자가의 정보 x, y, s를 한 줄에 하나씩 출력한다. x는 십자가 중심의 행의 번호, y는 열의 번호, s는 십자가의 크기이다.

가능한 답이 여러가지인 경우에는 아무거나 출력한다.

예제 입력 1

6 8
....*...
...**...
..*****.
...**...
....*...
........

예제 출력 1 

3
3 4 1
3 5 2
3 5 1

예제 입력 3 

5 5
.*...
***..
.*...
.*...
.....

예제 출력 3

-1

---

풀이방법

• 십자가가 들어갈 수 있는 공간을 모두 완전탐색 한다.
• visited 리스트를 만들어 한번 방문한 곳은 0으로 만든다. (visited의 초기 값은 별이 있는 위치만 1을 가짐)
• 현재 board[i][j] 위치에서 상, 하, 좌, 우 별이 있는지 체크한다. (checkStarCount)
  • 있다면 count를 1로 바꾸고 방문처리를 한다.
  • size를 하나씩 올려서도 십자가 인지 확인한다. 가장 큰 십자가만 있으면 된다. ( k(0 ≤ k ≤ N×M)  조건을 만족하기 위해. 예체출력 1번이 2개만 나와도 정답처리였음..)
• 최대 size는  size = min(i, n-i-1, j, m-j-1) 이 된다.

  • 

• 주의)

  

  checkStartCount에서 else 처리 안해준 경우 이 예문을 통과할 수 없음

import sys

# n은 행, m은 열
n, m = map(int, sys.stdin.readline().rstrip().split())

count = 0
answer = []

board = []
for i in range(n):
    board.append(list(sys.stdin.readline().rstrip()))

# 사용된 별인지 체크하기 위한 리스트
visited = [[0 for _ in range(m)] for _ in range(n)]

# 1인 곳은 별이 아직 사용 되지 않음.
for i in range(n):
    for j in range(m):
        if board[i][j] == '*':
            visited[i][j] = 1


def checkStarCount(i, j, size, visited):
    count = 0
    answer = []
    for s in range(1, size+1):
        if board[i-s][j] == '*' and board[i+s][j] == '*' and board[i][j-s] == '*' and board[i][j+s] == '*':
            count = 1
            answer = [i+1, j+1, s]
            visited[i][j] = 0
            visited[i-s][j] = 0
            visited[i+s][j] = 0
            visited[i][j-s] = 0
            visited[i][j+s] = 0
        else:
            return 1, answer
    return count, answer


for i in range(1, n-1):
    for j in range(1, m-1):
        # 중앙에 *인지 확인
        if board[i][j] == '*':
            # 가능한 최대 사이즈
            size = min(i, n-i-1, j, m-j-1)
            Acount, Aanswer = checkStarCount(i, j, size, visited)
            if Aanswer:
                answer.append(Aanswer)
                count += Acount

_sum = 0
for i in visited:
    _sum += sum(i)

if _sum == 0:
    # 정상 수행
    print(count)
    for i in answer:
        print(i[0], i[1], i[2])
else:
    print(-1)

---

후....