[WEEK03] DAY24 & 다익스트라 / DFS / BFS / 위상정렬 패턴

novxerim·2021년 11월 25일

BFS DFS 다익스트라(Dijkstra)알고리즘패턴 위상정렬

SW-Jungle

목록 보기

23/59

위상정렬

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)