알고리즘2 음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다. 코드 n,m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) def dfs(x, y): #그래프 이탈 시 if x = m: return False if graph[x][y] == 0: graph[x][y] =.. 2022. 3. 24. 다익스트라 다익스트라 알고리즘 시작노드에서 다른 임의의 노드까지의 최단 경로를 찾는 알고리즘이다. 최단 경로 찾기 문제에는 BFS을 활용한 알고리즘도 존재하지만 BFS는 노간간의 간선의 비용이 존재하지 않을 경우(모두 같을 경우) 사용되는 반면, 다익스트라 알고리즘은 간선의 비용이 모두 제 각각일 때 사용된다. 간선이 비용이 모두 다를 때의 최단 거리 알고리즘은 다익스트라 알고리즘뿐만 아니라 프로이드 워셜 알고리즘도 존재한다. 프로이드 알고리즘은 한가지의 시작노드만 계산하는 것이 아니라 모든 노드에서 출발하여 모든 노드로 가는 각각의 최단 경로를 구할 수 있다. 하지만 시간 복잡도가 O(N^3) 으로 높다. heapq 라이브러리를 사용하여 우선순위 큐를 이용한다. - 파이썬은 최소힙으로 구현되어있다. 필요한 구조 .. 2022. 3. 24. 이전 1 다음
