~์ค๋ฒ 2~
https://www.acmicpc.net/problem/16924
16924๋ฒ: ์ญ์๊ฐ ์ฐพ๊ธฐ
์ญ์๊ฐ๋ ๊ฐ์ด๋ฐ์ '*'๊ฐ ์๊ณ , ์ํ์ข์ฐ ๋ฐฉํฅ์ผ๋ก ๋ชจ๋ ๊ฐ์ ๊ธธ์ด์ '*'๊ฐ ์๋ ๋ชจ์์ด๋ค. ์ญ์๊ฐ์ ํฌ๊ธฐ๋ ๊ฐ์ด๋ฐ๋ฅผ ์ค์ฌ์ผ๋ก ์ํ์ข์ฐ ๋ฐฉํฅ์ผ๋ก ์๋ '*'์ ๊ฐ์์ด๋ค. ์ญ์๊ฐ์ ํฌ๊ธฐ๋ 1๋ณด๋ค ํฌ
www.acmicpc.net
[๊ตฌํ ํฌ์ธํธ]
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๋ฒ ์ญ์๊ฐ ์ฐพ๊ธฐ
์ญ์๊ฐ ์ฐพ๊ธฐ ์๊ฐ ์ ํ๋ฉ๋ชจ๋ฆฌ ์ ํ์ ์ถ์ ๋ต๋งํ ์ฌ๋์ ๋ต ๋น์จ 2 ์ด 512 MB 1432 562 415 38.858% ๋ฌธ์ ์ญ์๊ฐ๋ ๊ฐ์ด๋ฐ์ '*'๊ฐ ์๊ณ , ์ํ์ข์ฐ ๋ฐฉํฅ์ผ๋ก ๋ชจ๋ ๊ฐ์ ๊ธธ์ด์ '*'๊ฐ ์๋ ๋ชจ์์ด๋ค. ์ญ์๊ฐ
coolcode.tistory.com
https://codechacha.com/ko/python-convert-string-to-char-list/
Python - ๋ฌธ์์ด์ ํ ๊ธ์์ฉ ๋ถ๋ฆฌํ์ฌ ๋ฆฌ์คํธ์ ๋ฃ๊ธฐ
String์ ํ ๊ธ์์ฉ(char) ๋๋๊ณ , ๊ทธ ๋ฌธ์๋ค์ list๋ก ์ถ๊ฐํ ์ ์์ต๋๋ค. ์ด ๊ธ์์ 3๊ฐ์ง ๋ฐฉ๋ฒ์ ์๊ฐํฉ๋๋ค. list()์ ์ธ์๋ก ๋ฌธ์์ด์ ์ ๋ฌํ๋ฉด, ๋ฌธ์ ๋จ์๋ก ๋๋์ด list์ ์ ์ฅํฉ๋๋ค. for๋ฅผ ์ด์ฉ
codechacha.com