[Silver I] 십자가 찾기 - 16924

[Silver I] 십자가 찾기 - 16924

문제 링크

성능 요약

메모리: 48100 KB, 시간: 592 ms

분류

브루트포스 알고리즘, 구현, 시뮬레이션

제출 일자

2024년 11월 10일 01:34:56

문제 설명

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 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는 십자가의 크기이다.

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

 

풀이

import sys
from collections import deque 



N , M  = map(int, sys.stdin.readline().split())
global mat ,visitied
mat = [ [i for i in input()] for _ in range(N)]
visitied =  [[False] * M for _ in range(N)]

star_count = 0 
for x in range(N):
     for y in range(M):
          if(mat[x][y] == "*"):
               star_count += 1

def bfs(x,y):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    
    counts = []
    for w in range(4):
        nx = x 
        my = y
        
        count = 0
        while(True):
                nx += dx[w]
                my += dy[w]

                if nx < 0 or nx >= N or my < 0 or my >= M:
                    break

                if mat[nx][my] != '*':
                    break

                count +=1 
        counts.append(count)
    
    max_t = min(counts)
    
    if(max_t == 0):
         return
    else:
        visitied[x][y] = True
        for i in range(4):                 
            for c in range(1,max_t+1):
                    nx = x + dx[i] * c
                    my = y + dy[i] * c
                    if(nx < 0 or nx >= N or my < 0 or my >= M):
                        continue
                    else:
                        visitied[nx][my] = True
            
    return max_t


result = []

for i in range(N):
    for w in range(M):
        if(mat[i][w] == "*"):
                check_len = bfs(i,w)
                if(check_len != None):
                    for e in range(1,check_len+1):
                        tmp = []
                        tmp.extend([i+1, w+1, e])
                        result.append(tmp)


visitied_count = 0
for x in range(N):
     for y in range(M):
          if(visitied[x][y]):
               visitied_count += 1

if(visitied_count != star_count):
     print(-1)
else:
     print(len(result))
     for x,y,z in result:
          print(x , y, z)

 

테스트 케이스를 모두 통과했지만, matrix의 값이 모두 "*"인 경우를 생각하지 못했었다.

3 3
***
***
***

틀린 코드에서는 mat[x][y]가 "*"이면 무조건 일단 visitied를 True로 만들어버렸는데, 십자가 모양을 만들 수 있는 경우에만 True로 만드는 것으로 해결했다.