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

 

십자가 찾기 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

1432

562

415

38.858%

문제

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

예제 입력 2 복사

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

예제 출력 2 복사

3
2 2 1
3 3 1
3 4 1

예제 입력 3 복사

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

예제 출력 3 복사

-1

예제 입력 4 복사

3 3
*.*
.*.
*.*

예제 출력 4 복사

-1

 

 

---

풀이방법

• 입력받은 예제를 2차원 리스트로 만들어 inputList 에 저장합니다
• inputList 를 resultList(십자가를 지울 리스트) 에 딥카피를 이용 복사합니다
• inputList 의 위에서부터 '*' 을 찾아 상하좌우를 검사해 십자가를 찾고 십자가를 찾았을때는 resultList 에 십자가를 지워 줍니다
• 끝까지 다 검사했을때 십자가를 지운 리스트에 '*' 가 존재하는지 검사해 주고 존재할시 -1 아니면 count 갯수와 result 리스트를 출력해 줍니다

 

코드

---

 

import sys
import copy
 
a,b =map(int , sys.stdin.readline().split()) # 세로와 가로를 입력받음
inputList = [] #이차원배열을 넣을 리스트
for i in range(a):
    inputList.append(list(sys.stdin.readline().strip())) #리스트를 입력받아 삽입
 
finalList =copy.deepcopy(inputList) #딥카피를 통해 십자가를 그렸을경우 "*" 에서 "." 으로 바꿀 그래프를 만든다
count =0 # 십자가의 갯수
result =[] #(세로 , 가로 , 사이즈) 형태의 답을 넣을 리스트
for i in range(1, a):
    for j in range(1,b): #맨윗줄부터 아랫줄로 이어지는 for문
        size = 0 #사이즈를 초기화
        if (inputList[i][j]=='*'): #받은 리스트 에  '*' 이 존재할시
            up=down =i
            left=right=j
            #현재 위치를 저장
 
            while(1): # 십자가가 없을때까지 루프
                up= up-1 #상하좌우 좌표를 가져옴
                down =down+1
                left = left-1
                right = right+1
 
                if(up>=0 and down<a and left>=0 and right<b and inputList[up][j] =='*' and inputList[down][j] =='*'and inputList[i][left] =='*' and inputList[i][right] =='*' ):
                    #상하좌우가 리스트의 크기를 넘어가지 않고 '*' 일때
                    finalList[up][j] =finalList[down][j] =finalList[i][left] =finalList[i][right]=finalList[i][j] ='.' # 십자가를 그렸음으로 십자가의 위치 값을 '*' 에서 '.' 으로 바꿔준다
                    size = size + 1 #사이즈 상승  그후
                else: #더이상 십자가가 없을때
                    if(size>0): #사이즈가 0보다 클때 즉  1이상의 크기를 가진 십자가를 현재 위치에서 찾을 수 있을때
                        result.append("{0} {1} {2}".format(i+1 ,j+1,size)) #result 리스트에 (세로 , 가로 , 사이즈) 형태로 삽입한다
                    break
        if(size !=0): #사이즈가 0이 아닐때 즉 하나의 십자가를 찾았을때 count 값을 추가해준다
            count =count+1
check = True # 십자가를 그린 리스트 finalList 에 '*' 이 존재 하는지 확인하기 위한 boolean 값
for i in finalList:
    if '*'in i:
        print(-1)
        check=False #십자가를 다그렸음에도 '*' 가 남아있는경우 에는 False 값을 주고 -1 을 출력한다
        break
if(check):
    print(count) #십자가를 다그려 '*' 가 남아있지않은경우 십자가의 갯수와 result 리스트를 출력한다
    for i in result:
        print(str(i))