원글 페이지 : 바로가기
https://velog.io/@yerimii11/WEEK03-DAY24-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-DFS-BFS-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-%ED%8C%A8%ED%84%B4 2021년 11월 25일에 작성된 게시글 아카이브입니다. (사유: 블로그이전) [WEEK03] DAY24 & 다익스트라 / DFS / BFS / 위상정렬 패턴 https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093https://suri78.tistory.com/202경로를 여러군데 거친 최종 최소 거리를 구해야 할 때 사용BF velog.io 위상정렬 https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093 https://suri78.tistory.com/202 다익스트라 경로를 여러군데 거친 최종 최소 거리를 구해야 할 때 사용 BFS BFS로 풀이시 : 큐 사용 할 때 대부분 visit / need_visit(visited) 두 개 리스트를 만들어서 팝하고 체크하는 식으로 시작하는 듯 내 근처에 있는 애들 먼저 순차적으로 다 탐색한다 BFS / DFS https://velog.io/@jewon119/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS#4-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89bfs 다익스트라 vs 위상정렬 내 정리 다익스트라 / DFS / BFS 패턴 위상정렬 패턴 . . Team 활동 (코드 리뷰) 1916 최소비용구하기 / 2665 미로만들기 / 7569 토마토 / 3055 탈출 / 2294 동전2 2252 줄 세우기 / 2637 장난감조립 . 2252 줄 세우기 (위상 정렬) 코드 import sys
input = sys.stdin.readline
from collections import deque
Vn, En = map(int, input().split())
parent = [0 for i in range(Vn + 1)]
V = [[] for i in range(Vn + 1)]
for i in range(En) :
a, b = map(int, input().split()) # 앞에 숫자가 순서상 앞이니까 big=a
V[a].append(b) #인접리스트에 삽입
parent[b] = parent[b] + 1
que = deque()
for i in range(1, Vn + 1) :
if parent[i] == 0 : # 부모노드가 없는 애들 먼저 큐에 넣음
que.append(i) # 1, 2
while que :
now = que.popleft()
print(now, end = ‘ ‘)
for next in V[now] : # now의 인접노드 -> next
parent[next] = parent[next] – 1 # 간선을 하나씩 지움
if parent[next] == 0 : # 간선이 0개가 되면
que.append(next) # 그 숫자로 큐에 넣음 / 마지막에 3 들어가서 que 한 번 더 돔 2637 장난감조립 (위상정렬) 14888 연산자 끼워넣기 (DFS) 형광펜 쳐둔 부분에 한 줄 컷으로 조건을 달아놓은 것이 인상적이어서 나도 써먹어봤다 코드 # from os import device_encoding
import sys
input = sys.stdin.readline
def cal(count, result, plus, minus, mulitiply, divide):
global max_result
global min_result
if count == n:
max_result = max(max_result, result)
min_result = min(min_result, result)
return
else:
if plus:
cal(count+1, result + nums[count], plus – 1, minus, mulitiply, divide)
if minus:
cal(count+1, result – nums[count], plus, minus – 1, mulitiply, divide)
if mulitiply:
cal(count+1, result * nums[count], plus, minus, mulitiply – 1, divide)
if divide: # 추가해야할 조건) 음수를 양수로 나눌 땐 양수로 바꿔서 계산한 후 나온 몫을 음수로 바꾼다
cal(count+1, -(-result // nums[count]) if result < 0 else result // nums[count], plus, minus, mulitiply, divide - 1)
# +가 2개 올 수도 있는데? -> plus 라는게 들어오는지 확인하려면?
if __name__ == ‘__main__’:
n = int(input())
nums = list(map(int, input().split())) # 계산할 숫자
calculate = list(map(int, input().split()))
max_result = float(‘-inf’)
min_result = float(‘inf’)
# result = []
# nums(x) nums[0] ?
cal(1, nums[0], calculate[0], calculate[1], calculate[2], calculate[3])
print(max_result)
print(min_result)
. 2573 빙산 . 1432 그래프 수정 (위상 정렬) . 1948 임계경로 (위상 정렬) . . 너무 피곤하다!!!! 시험 화이팅