[백준/16924/파이썬] 십자가 찾기

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

16924번: 십자가 찾기

Problem

• 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 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는 십자가의 크기이다.
• 가능한 답이 여러가지인 경우에는 아무거나 출력한다.

SOL

생각보다 까다로운 문제였다. 처음에 문제를 잘못이해해서, 최소한의 십자가로 만들 수 있는 경우를 생각해줬다가, 그냥 단순히 브루트포스(완전탐색)을 해주면 되는 문제인걸 깨달았다.

 

1. "*"인 지점을 1로 모두 기록 해놓는다.
2. 그 다음 ,"*"인 지점을 시작으로 bfs를 돌린다.(십자가로 채우기 시작!)
   • BFS 탐색할 때, 길이가 1~M까지 가능한 모든 십자가를 탐사해준다. (N,M 대소관계는 상관없다. 어차피 작은거 따라간다) 
   • 범위 체크를 해준다. 만약, 십자가가 가능하다면, flag를 그대로 true로 해주고, pass해준다.
   • flag가 True(크로스를 만들 수 있다면), visited에 기록해둔 1을 지운다.
3. 다 채우고 나서, visited에 1이 그대로 남아있다면(채워지지 못하고) 이건 못채우는 경우라서, -1를 출력하는 형식으로 구현했다.
4. 십자가의 길이를 늘릴 때, N,M 중 작은걸 자동으로 따라가기 때문에, N,M 둘중에 뭘 설정해주어도 상관이 없다.
5. (어차피, 범위 조건과 "*"이라는 조건 때문에 알아서 걸러진다. 사실 이 부분 때문에, 고민을 많이 하다가, N,M 둘 다 테스트를 해봤는데 딱히 상관이 없어서 M으로 구현했다.)

import sys
input= sys.stdin.readline
from collections import deque

N,M =map(int,input().split())
board=[list(input().rstrip()) for _ in range(N)]
visited=[[0 for _ in range(M)] for _ in range(N)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
ans=[]

def bfs(y,x):
    for s in range(1,M):
        flag = True
        for k in range(4):
            ny=y+dy[k]*s
            nx=x+dx[k]*s
            if 0<=ny<N and 0<=nx<M and board[ny][nx] =="*":
                pass
            else:
                flag=False
                break
        if flag:
            ans.append([y+1,x+1,s])
            for i in range(4):
                ny=y+dy[i]*s
                nx=x+dx[i]*s
                visited[ny][nx] =0
            visited[y][x] =0
        else:
            break

for i in range(N):
    for j in range(M):
        if board[i][j] =="*":
            visited[i][j]=1

for i in range(N):
    for j in range(M):
        if board[i][j] =="*":
            bfs(i,j)

total =0
for i in range(N):
    for j in range(M):
        total +=visited[i][j]

if total==0:
    print(len(ans))
    for an in ans:
        print(*an)
else:
    print(-1)