동빈북
백준 18352번 특정 거리의 도시 찾기 실버2
- 문제
- 최종풀이
- 0417풀이-파이썬
- 0420풀이-자바
- 오랜만에 풀었는데 푼 방법이 똑같아서 뿌듯했다
이전풀이
깊이 우선탐색 이라고 생각했다. 문제를 풀다보니 너비 우선탐색인 것을 알아냈다. - 너비 탐색에서 어려운것은 항상 그 레벨을 표시하는 방법 같다. 옛날에도 이 비슷한 문제 봤었는데 외워야 겠다.
동빈북 해설
- '모든 도로의 거리는 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() 해줘야 한다.
spring, java학습