완전탐색
-
가능한 모든 경우의 수를 탐색하는 유형이다
-
재귀 형태로 문제를 푸는경우가 많으며, 각 단계마다 가능한 경우는 다음 재귀를 실행시키고 불가능한경우는 넘어간다
-
재귀의 끝 (탈출조건)에 도달했을 때, 1을 리턴해 경우의 수를 카운트한다
-
경우의 수를 세는 문제는 완전탐색 유형이다
-
브루트 포스는 완전 탐색 알고리즘이다
- 선형구조는 순차 탐색
비선형구조는 DFS 또는 BFS 를 이용한다
-
즉, for 문 돌면서 하나씩 조건 체크하는 방식으로 문제를 풀거나
-
DFS, BFS 등을 사용해가며 문제를 푼다
노트
풀이
십자가끼리 겹쳐도 되고, 가능한 답을 출력만 하면 되는 문제라서
1) N x M 전체를 탐색해가며 최대로 놓을 수 있는 크기의 십자가를 놓고
2) 최종 상태 확인하는 방식으로 푼다
문제점
십자가를 놓아가면서 가능한 경우의 수를 탐색하고, 실패하면 다시 복원해서 다른 경우의 수를 시도해보는
문제라고 생각했었다.
- 모든 경우의 수를 재귀로 시도했었는데, 가능한 경우 중 아무거나 출력하면 돼서 최대 사이즈만 시도했어야 했다.
- 재귀로 풀고싶었으면 아래처럼 풀면 될듯
1) 완전탐색을 재귀로 돌면서 한 점도 빠지지 말고 돌고
2) * 인 경우 최대 사이즈 십자가를 테스트하고
3) 재귀 시작 부분에서 성공 여부 테스트하고
4) 재귀 끝부분에서 답 리턴하고
십자가끼리 겹쳐도 되고, 가능한 답을 출력만 하면 되는 문제라서
N x M 전체를 탐색해가며 최대로 놓을 수 있는 크기의 십자가를 놓고
최종 상태 확인하는 방식으로 푼다
코드
import sys
sys.stdin = open('16924.txt')
n, m = list(map(int,input().split()))
data = ['' for _ in range(n)]
for i in range(n):
line = input()
data[i] = line
check = [[False for _ in range(m)] for _ in range(n)]
# for 문 사용해서 완전탐색
# 채울 수 있는 모든 곳을 최대 크기의 십자가로 채운다
ans = set()
for i in range(n):
for j in range(m):
if data[i][j] == '.':
continue
max_size = 0
dl = 1
while True:
if i - dl < 0 or i + dl >= n or j - dl < 0 or j + dl >= m:
break
if data[i-dl][j] == '.' or data[i+dl][j] == '.' or data[i][j-dl] == '.' or data[i][j+dl] == '.':
break
max_size = dl
dl += 1
if max_size != 0:
check[i][j] = True
for k in range(1, max_size + 1):
check[i+k][j] = True
check[i-k][j] = True
check[i][j+k] = True
check[i][j-k] = True
ans.add((i+1, j+1, max_size))
# 문제 요구사항 만족 여부 체크
for i in range(n):
for j in range(m):
if data[i][j] == '*' and not check[i][j]:
print(-1)
exit()
print(len(ans))
for d in ans:
print(' '.join(list(map(str,d))))
