[알고리즘/백준] Brute Force - 2309번 일곱난쟁이 / 17086번 아기상어2

브루트 포스 - 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함수와 사용 방법은 동일하나, 함수의 결과가 참인지 거짓인지에 따라, 해당 요소를 포함할지를 결정

출처 : https://wikidocs.net/22803