[Python][백준] 16924_십자가 찾기

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

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는 십자가의 크기이다.

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

---

BFS를 사용한 완전탐색기법으로 아래와 같이 문제풀이를 진행했다.

 

(1) 십자가 찾기

- arr를 순회하며 '*'를 찾고, bfs로 사방탐색값이 '*'이면 que에 좌표, 길이정보 리스트를 담는다.

- que에 쌓인 갯수가 4개일 경우 result arr에 값을 추가한다.

- 방향성으로 bfs 다시 수행 --> que 갯수가 4보다 작아질 때까지 반복하며 result에 값을 추가한다.

 

(2) 십자가로만 입력값을 만들 수 있는지 판단

- 전체 '*'의 갯수 (starNum)와 십자가를 체크한 vi 항목의 '1' 갯수가 동일한지 확인

- result arr의 갯수가 0이 아닌지 확인

--> 두개를 다 만족하지 않을 경우 '-1' 출력

 

import sys
from collections import deque

def bfs(i, j):
    global res

    que = deque()
    for n in range(4):
        ni,nj = i + di[n], j + dj[n]
        if ni >= 0 and ni < N and nj >= 0 and nj < M and arr[ni][nj] == '*':
            que.append([ni, nj, n])
        if len(que) == 4:
            vi[i][j] = 1

    l = 1
    while(len(que) == 4):
        res.append(str(i+1) + " " + str(j+1) + " " + str(l))

        for n in range(4):
            item = que.popleft()
            vi[item[0]][item[1]] = 1
            ni, nj = item[0] + di[item[2]], item[1] + dj[item[2]]
            if ni >= 0 and ni < N and nj >= 0 and nj < M and arr[ni][nj] == '*':
                que.append([ni, nj, n])
        l+=1


## MAIN
di, dj = [0, 1, 0, -1], [1, 0, -1, 0]
starNum = 0

N, M = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().strip()) for n in range(N)]
vi = [[0 for _ in range(M)] for _ in range(N)]
res = []

for i in range(N):
    for j in range(M):
        
        if arr[i][j] == '*':
            starNum += 1
            bfs(i, j)

starSum = 0
for i in range(N):
    starSum += sum(vi[i])

if len(res) == 0 or starNum != starSum:
    print(-1)
else:
    print(len(res))
    for r in res:
        print(r)