[03.31/week03]TIL

오늘 한줄 요약

무언가 넣었는데 100%로 남아있지 않다...ㅠ

오늘 공부한 것

• 최단경로 알고리즘
• dx, dy 테크닉

새로 배우게 된 것

최단경로 알고리즘

1. 다익스트라 알고리즘

한 정점에서 다른 정점까지 최단 경로를 구하는 알고리즘(one to ALL)

• 동작 단계

1. 출발 노드와 도착 노드 설정
2. 최단 거리 테이블초기화
3. 현재 위치한 노드와 인접한 모든 노드의 최단 거리 값을 갱신한다.
4. 모든 미방문 노드 중 최단 거리 테이블의 값이 가장 작은 노드를 선택한다.
5. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산, 최단 거리 테이블 업데이트
6. 3번과 4번 과정 반복

• 음수가 있으면 안되는 이유?
  다익스트라는 어떤 정점으로의 최단거리를 계산하면 그것이 확정된 값이라고 믿는다.
  이때 음수 간선이 있다면 추후 그 음수 간선을 거쳐서 더 짧은 거리가 나올 수 있기 때문에 음수 가중치가 있으면 안된다.

• 파이썬 구현
  구현 방식은 두가지로 방문하지 않은 노드를 다루는 방식에서 순차탐색과 우선순위 큐로 나뉘는데 시간 복잡도가 더 빠른 우선순위 큐로 구현해보았다.

import heapq
def dijikstra_prorityQ(start):
  queue = []
  heapq.heappush(queue, (0, start))
  distance[start] = 0
  while queue:
    dist, node = heapq.heappop(queue)
    # 큐에서 뽑아낸 거리가 이미 갱신 된 거리보다 클 경우 무시
    if distance[node] < dist:
      continue
    # 큐에서 뽑아낸 노드와 연결된 인접 노드 탐색
    for next in graph[node]:
      cost = distance[node] + next[1] # start ~ node + node ~ next 
      if cost < distance[next[0]]: 
        distance[next[0]] = cost
        heapq.heappush(queue, (cost, next[0]))

2. 플로이드 워셜

모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘(all - to - all)

• 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행( 다익스트라와 달리 미방문 노드 중 최단거리 갖는 노드를 찾을 필요가 없음)
• 2차원 테이블에 최단 거리 정보저장
• DP 알고리즘에 해당 (다익스트라는 그리디)

INF = 1e9

# 노드의 개수 및 간선의 개수 입력
V = int(input())
E = int(input())

# 2차원 그래프 만들고 무한으로 초기화
graph = [[INF] * (V + 1) for _ in range(V + 1)]

# 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
for start in range(1, V + 1):
  for end in range(1, V + 1):
    if start == end:
      graph[start][end] = 0

# 각 간선에 대한 정보를 입력받고, 그 값으로 초기화
for _ in range(E):
  # A에서 B로 가는 비용
  start, end, price = map(int, input().split())
  graph[start][end] = price

# 점화식에 따라 Floyd-Warshall 수행
for k in range(1, V+ 1):
  for a in range(1, V + 1):
    for b in range(1, V + 1):
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for start in range(1, V + 1):
  for end in range(1, V + 1):
    # 도달 불가일 경우 INF 출력
    if graph[start][end] == 1e9:
      print('INF')
    # 도달 가능하면 거리 출력
    else:
      print(graph[start][end], end=' ')

3. 벨만 포드 알고리즘

음수 가중치를 가진 간선이 있다면 다익스트라 말고 벨만 포드를 사용해야 한다.

• 수행 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 아래 단계 V- 1 번 반복
   1. 모든 간선 E개 하나씩 확인
      1. 각 간선을 거쳐 다른 노드로 가는 비용을 계산 ⇒ 최단 거리 테이블을 갱신
   2. 만약 음수 간선 순환 발생하는지 체크 하고 싶다면 3번과정을 한 번 더 수행
      1. 이때 최단 거리 테이블이 갱신된다면 음수 간선 존재

BellmanFord(G,w,s):
//초기화 과정
for each u in G.V:     //노드를 초기화 하기
      distance[v] = inf      //모든 노드의 최단거리를 무한으로 지정
      parent[v] = null       //모든 노드의 부모 노드를 널값으로 지정
distance[s] = 0 //출발점의 최단거리는 0으로 지정한다
//거리측정 과정
for i from 1 to len(G.V):   //노드의 숫자만큼
     for each (u,v) in G.E:   //모든 변을 체크해 최단 거리를 찾아본다.
          if distance[u] + w[(u,v)] < distance[v]:   
          //만약 u를 경유하여 v로 가는 거리가 현재 v의 최단 거리보다 짧으면
               distance[v] = distance[u] + w[(u,v)]  //그 거리를 v의 최단거리로 지정
               parent[v] = u   //u를 v의 부모 노드로 지정
//음수 사이클 체크 과정
for each (u,v) in G.E:
     if distance[u] + w[(u,v)] < distance[v]:
          return false //음수 사이클을 확인하고 알고리즘을 정지
return distance[], parent[]

dx, dy 테크닉

코딩테스트 문제를 풀면서 좌표가 주어지고, 이를 기준으로 인접한 노드를 탐색할 경우 유용하게 쓸 수 있는 테크닉.

x,y 좌표의 변화를 리스트에 담아서 상,하,좌,우 이동을 편리하게 할 수 있다.

• Dx, dy + BFS 결합
  BFS 탐색시 dx, dy 테크닉을 결합하여 벽을 벗어나지 않고, 범위 내 노드 중 1이 들어있는 영역을 만나면 큐에 삽입하여 BFS 를 실행하는 코드.

dx = [-1, 1, 0, 0] 
dy = [0, 0, -1, 1]

def bfs(x, y):
    
    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
    
    return graph[n-1][m-1]

공부하다가 아쉬운 점

월요병인가 집중도가 제일 낮았던 날.
화요일은 심기일전해서 다시 집중해보자