브루트 포스 - Brute(무식한) + Force(힘)
: 완전 탐색 알고리즘
가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져온다.
참고 : https://codesyun.tistory.com/79
2039번 일곱난쟁이 - https://www.acmicpc.net/problem/2309
접근 방법
- itertools.permutations 함수 사용
파이썬으로 풀었기 때문에 가능한 것 같은 풀이라 아쉽다.
import itertools
height = []
for i in range(9):
height.append(int(input()))
for key in list(itertools.permutations(height, 7)):
if sum(key) == 100:
answer = key
break
for i in sorted(answer):
print(i)
다른사람의 풀이
아홉 난쟁이 키 합에서 두명의 난쟁이 키를 뺀 합이 100인것을 판별하도록 한다.
그리고 리스트를 찾으면 2명의 난쟁이 키 값을 리스트에서 삭제
17086번 아기상어2 - https://www.acmicpc.net/problem/17086
접근 방법
아기상어가 있는 좌표에서부터 퍼져나가면서 안전거리를 구한다.
처음에는 아래의 코드처럼 좌표마다 함수를 돌려서 새로 안전거리 리스트를 만들어주었다.
하지만 이렇게 풀면 python3로 돌리면 시간초과 / pypy3로 돌리면 통과지만 시간이 오래걸린다. ( 134956KB / 1116ms )
def safe_space(space, x, y):
visited = [[0] * M for _ in range(N)]
queue = deque([(x, y)])
space[x][y] = 0
visited[x][y] = 1
while queue:
node = queue.popleft()
for a, b in [(0, 1), (1, 0), (1, 1), (1, -1), (0, -1), (-1, 0), (-1, -1), (-1, 1)]:
if positive_space(node[0] + a, node[1] + b):
space[node[0]][node[1]] = min(space[node[0]][node[1]], space[node[0]+a][node[1]+b] + 1)
if visited[node[0] + a][node[1] + b] == 0:
visited[node[0] + a][node[1] + b] = 1
queue.append((node[0] + a, node[1] + b))
return space
for a, b in baby_shark:
safe = safe_space(safe, a, b)
그래서 각 좌표를 처음부터 queue에 넣고 시작하도록 코드를 변경하였다.
변경 결과 python3로 통과되었다. ( 33016KB / 112ms )
최종 제출 코드
from collections import deque
def positive_space(x, y):
if 0 <= x < N and 0 <= y < M:
return True
return False
def safe_space(space, baby_shark):
visited = [[0] * M for _ in range(N)]
queue = deque(baby_shark)
for x, y in baby_shark:
space[x][y] = 0
visited[x][y] = 1
while queue:
node = queue.popleft()
for a, b in [(0, 1), (1, 0), (1, 1), (1, -1), (0, -1), (-1, 0), (-1, -1), (-1, 1)]:
if positive_space(node[0] + a, node[1] + b):
space[node[0]][node[1]] = min(space[node[0]][node[1]], space[node[0]+a][node[1]+b] + 1)
if visited[node[0] + a][node[1] + b] == 0:
visited[node[0] + a][node[1] + b] = 1
queue.append((node[0] + a, node[1] + b))
return space
N, M = map(int, input().split())
baby_shark = []
space = [[] for _ in range(N)]
for i in range(N):
space[i] = list(map(int, input().split()))
for j in list(filter(lambda x: space[i][x] == 1, range(M))): #filter와 lambda
baby_shark.append((i, j))
safe = [[51] * M for _ in range(N)]
safe = safe_space(safe, baby_shark)
print(max(map(max, safe)))
다른사람의 풀이 : https://rebas.kr/798 --> 깔끔하게 푸신 느낌
공부한 문법
- 2차원 배열의 최댓값/최솟값 구하기
list_name = max(map(max, list_name))
list_name = min(map(min, list_name))
- list에서 value 값으로 다중 index 찾기
: filter와 lambda 사용
filter(lambda x: space[i][x] == 1, range(M))
filter 함수 : filter(적용시킬 함수, 적용할 요소들)
filter함수는 특정 조건으로 걸러서 걸러진 요소들로 iterator객체를 만들어서 리턴
map함수와 사용 방법은 동일하나, 함수의 결과가 참인지 거짓인지에 따라, 해당 요소를 포함할지를 결정
'study > 알고리즘' 카테고리의 다른 글
[알고리즘/프로그래머스] Level 1 끝 ! (0) | 2022.01.11 |
---|---|
[알고리즘/프로그래머스] 소수 찾기 (0) | 2022.01.07 |
[알고리즘/프로그래머스] 퍼즐 조각 채우기 (0) | 2021.12.27 |
[알고리즘/프로그래머스] 전력망을 둘로 나누기 (0) | 2021.12.23 |
[알고리즘/프로그래머스] 교점에 별 만들기 (0) | 2021.12.21 |