[Python] 백준 16924 십자가 찾기 | 완전 탐색 | 브루트포스(Brute-force)

~실버 2~

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

16924번: 십자가 찾기

 

 

[구현 포인트]

1. 제공된 입력 외 십자가 발견시 '*'을 '.'으로 변경할 공간 deepcopy

2. 완전탐색하며 '*' 발견시 인덱스를 넓혀 십자 모양 확인

3. 2를 십자 모양일 때까지 반복

- 반복마다 사이즈 += 1

- 리스트형 변수에 (i, j, size) 추가

- 십자 모양에 대해 '.' 처리

4. 완전탐색 후 십자모양으로 '.'처리한 공간에 '*'가 있다면 -1 반환

5. 그렇지 않다면 result의 크기와 값들 출력

+

 필자는 문자열을 리스트로 저장하는 방법이 헷갈려서 찾아보았었다.

 

---

[최종코드]

import sys
import copy

input = sys.stdin.readline

N, M = map(int, input().split())
result = []
board = []

for _ in range(N):  # 입력을 board에 저장
    line = list(input())
    board.append(line)

tempBoard = copy.deepcopy(board)  # '*' -> '.' 처리할 공간, 단순 copy시 주소값으로 저장함
for i in range(1, N):
    for j in range(1, M):
        if board[i][j] == '*':  # 십자의 중심이 될 수도 있는 위치
            up = down = i
            left = right = j
            size = 0
            while True:  # 십자 모양일 때까지 반복
                up -= 1
                down += 1
                left -= 1
                right += 1
                if up >= 0 and down < N and left >= 0 and right < M and board[up][j] == '*' and board[down][j] == '*' and \
                        board[i][left] == '*' and board[i][right] == '*':
                    size += 1
                    tempBoard[up][j] = tempBoard[down][j] = tempBoard[i][left] = tempBoard[i][right] = '.'
                    result.append((i + 1, j + 1, size))
                else:  # 더이상 십자 모양이 아닐 때
                    if size > 0:  # 십자 모양이 하나 있었을 때 중심을 '.'로 변경
                        tempBoard[i][j] = '.'
                    break

temp = True  # 십자모양으로 지워지지 않은 '*'가 있는지 확인할 변수
for t in tempBoard:
    if '*' in t:
        temp = False
        print(-1)
        break
if temp:  # 십자모양으로 모든 '*'을 지운 경우
    print(len(result))
    result.sort(key=lambda x: (x[0], x[1], -x[2]))
    for r in result:
        print(r[0], r[1], r[2])

 

 

 

 

 

 

 

 

---

REFERENCE

https://coolcode.tistory.com/5

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

https://codechacha.com/ko/python-convert-string-to-char-list/

Python - 문자열을 한 글자씩 분리하여 리스트에 넣기