211013 수 Algorithms TIL
동빈북
특정거리의 도시찾기 bfs
이전풀이
깊이 우선탐색 이라고 생각했다. 문제를 풀다보니 너비 우선탐색인 것을 알아냈다. - 너비 탐색에서 어려운것은 항상 그 레벨을 표시하는 방법 같다. 옛날에도 이 비슷한 문제 봤었는데 외워야 겠다.
동빈북 해설
- '모든 도로의 거리는 1'이라는 조건 덕분에 너비 우선탐색
- 모든 간선의 비용이 동일할 때는 너비우선탐색을 이용하여 최단 거리를 찾을 수 있다.
두 번째 풀 때 1208
풀이를 안보고 풀때 풀이가 또 달랐다. bfs를 이용하긴 했으나 최단 거리를 계속 갱신해줬다.
동빈북은 이미 방문 했다면(거리가 최대가 아닐 때) 따져줄 필요가 없다고 생각한 것 같다. 어차피 bfs니까 레벨별로 검사하니까 앞에서 검사하는 친구가 최소 값일 것이다.
그러나 시간초과는 계속 되었다.
왜 시간 초과가 계속 되나 했더니 distance 집합 안에 이미 target이 있는지 확인을 먼저 해주고 없다면 -1을 재빠르게 해줘야 했던 부분
요기 때문이었다. ㅎㅎ
연구소
완전탐색, dfs, 구현
- 바이러스 퍼진 곳에는 울타리를 세울 수 없다.
- 이 조건을 몰라서 헤매었다.
문제풀이
- 벽을 세우는 문제를 나는 : combinations으로 동빈북은 dfs(재귀)를 이용해서 풀었다.
def dfs(count):
global result
# 울타리가 3개 설치된 경우
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
# 각 바이러스의 위치에서 전파 진행
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
# 안전 영역의 최대값 계산
result = max(result, get_score())
return
# 빈 공간에 울타리를 설치
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
dfs(count)
data[i][j] = 0
count -= 1
경쟁적 전염 bfs
프로그래머스
dictionary의 키는 set, list 불가능 immutable한 tuple만 가능
- set은 dictionary의 키로 넣을 수가 없다.
TypeError: unhashable type: 'set'
https://stackoverflow.com/questions/23577724/type-error-unhashable-typeset
- immutable한 object이 아니기 때문이라고 한다.
- 찾아보니 list도 마찬가지라고 한다.
- 이 때, list나 set을 tuple로 바꿔주면 된다고 한다.
- https://daewonyoon.tistory.com/363
- 튜플을 변경할 수 없기 때문에
- 튜플로 바꾸기
a = [1,2,3]
a = tuple(a)
tuple을 정렬하기
https://codechacha.com/ko/python-sort-tuple/
- tuple은 ('a', 'b)와 ('b', 'a)가 다르다고 나온다. 이 둘을 같은 객체로 취급하고 싶어서 정렬을 해주고 싶었다.
x = ('a', 'b')
x = tuple(sorted(x, key = lambda x : x))
- tuple을 정렬시에 다시 tuple로 만들고 싶다면 tuple() 해줘야 한다.
Author And Source
이 문제에 관하여(211013 수 Algorithms TIL), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bongf/211013-Algorithms-TIL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)