[Python] 백준 1753, 프로그래머스 게임 맵 최단거리, 프로그래머스 네트워크, 프로그래머스 배달

오늘은 최단 거리 알고리즘에 대해 공부하며 관련 문제를 풀었다.

코딩테스트에서 나오는 대표적인 알고리즘은 "다익스트라", "벨만포드" 알고리즘이다.

1. 문제: https://www.acmicpc.net/problem/1753

다익스트라 알고리즘

- 하나의 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘

- 가중치가 양의 정수로만 이루어져있을 때 사용 가능한 알고리즘

- 우선순위 큐(Heap) 사용하여, 가장 비용이 적은 경로를 먼저 탐색

 

✅ 풀이

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)
v, e = map(int, input().split())  # 정점의 갯수 v, 간선의 갯수 e
start = int(input())

graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)   # 시작노드부터 특정 노드까지의 최소비용 저장 테이블 --> 초기에는 모두 INF로 초기화함

for _ in range(e):
  u, v, w = map(int, input().split())
  graph[u].append((v, w))   #u에서 v로 가는 가중치 w인 간선

def dijkstra(start):
  q = []
  distance[start] =  0    # 시작노드의 최단 거리를 0으로 초기화
  heapq.heappush(q, (0, start))   # 맨 처음 인접노드로 시작 노드 추가

  while q:
    dist, now = heapq.heappop(q)

    if distance[now] < dist:  # 이미 방문한 노드인 경우 건너뜀
      continue

    for i in graph[now]:   # 현재 노드의 인접한 노드 중에
      cost = dist + i[1]   # 기존의 거리에 인접한 노드의 가중치를 더한 값이

      if cost < distance[i[0]]:    # 기존의 최단 거리보다 작으면?
          distance[i[0]] = cost    # 갱신
          heapq.heappush(q, (cost, i[0]))    # 해당 인접 노드 및 거리 추가

dijkstra(start)

for i in range(1, len(distance)):
  if distance[i] == INF:
    print("INF")
  else:
    print(distance[i])

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/1844

그래프가 주어지고, "캐릭터가 0, 0부터 시작하여 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸 갯수의 최소값" 이므로 바로 BFS를 떠올렸다.

 

✅ 풀이

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    distance = [[-1] * m for _ in range(n)]   
    # 방문 여부와 거리 정보를 저장하기 위한 2차원 배열로, 초기에는 방문하지 않았음을 표시하기 위해 -1로 초기화한다.
    
    dx = [-1, 1, 0, 0]   # 상, 하, 좌, 우로 이동하는 데 도움을 주기 위한 이동 배열
    dy = [0, 0, -1, 1]

    def bfs(x, y):
        q = deque([(x, y)])
        distance[x][y] = 1   # 시작을 1로 할당하여 방문처리함

        while q:
            now_x, now_y = q.popleft()

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

 			# 1) 범위 체크 2) 벽이 아닌지 체크 3) 방문 여부 체크
                if 0<=nx<n and 0<=ny<m and maps[nx][ny] != 0 and distance[nx][ny] == -1:
                    q.append((nx, ny))
                    distance[nx][ny] = distance[now_x][now_y] + 1   # 이전거리에서 + 1
                    
        return distance
    
    bfs(0, 0)    # 시작점: 0, 0
        
    return distance[n-1][m-1]

 

3. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/43162

해당 문제는 DFS, BFS로 모두 풀이 가능한 유형이다.

노드 간 연결되어있는 네트워크의 갯수, 즉 영역의 갯수를 세는 문제이다. (영역의 갯수 = 그래프 탐색을 시행한 횟수)

 

✅ DFS 풀이

def solution(n, computers):
    answer = 0
    
    visited = [False] * n
    
    def dfs(v):
        visited[v] = True
        
        for i in range(n):   # 인접한 노드 중 방문하지 않은 노드에 대해 DFS 실행
            if i != v and not visited[i] and computers[v][i] == 1:
                dfs(i)
        
        
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer += 1   # 탐색 실행할때마다 + 1
        
    return answer

 

✅ BFS 풀이

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n

    def bfs(v):
        q = deque([v])
        visited[v] = True
        
        while q:
            node = q.popleft()
        
            for i in range(n):
                if i != node and not visited[i] and computers[node][i] == 1:
                    q.append(i)
                    visited[i] = True
        
        
    for i in range(n):
        if not visited[i]:
            bfs(i)
            answer += 1
        
    return answer

 

그리고 위 코드에서 탐색 할때의 for문을 아래와 같이 enumerate를 활용하여 개선할 수 있다.

enumerate(list)는 인덱스와 요소를 함께 접근할 수 있는 메서드이다.

for i in range(n):
    if i != v and not visited[i] and computers[v][i] == 1
    
 
for idx, connected in enumerate(computers[v]):
	if idx != v and not visited[idx] and connected:

 

4. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/12978

마을과 마을 간 걸리는 시간 -> 양수 가중치

1번 마을에 있는 음식점이 K이하의 시간에 배달이 가능한 마을의 갯수 -> 1번 마을에서 각 마을 배달까지 걸리는 최단 시간

을 종합했을 때 다익스트라를 활용하는 문제이다.

 

✅ 풀이

import heapq

def solution(N, road, K):
    INF = int(1e9)
    distance = [INF] * (N+1)
    graph = [[] for _ in range(N+1)]
    q = []
    
    for r in road:
        graph[r[0]].append((r[1], r[2]))   # 양방향으로 연결
        graph[r[1]].append((r[0], r[2]))
    
    distance[1] = 0   # 1번 마을에서 시작
    heapq.heappush(q, (0, 1))    # 1번 마을이 시작점이므로, 0으로 초기화
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:   # 이미 최단거리를 계산한 마을이라면 pass
            continue
            
        for i in graph[now]:     # 인접한 모든 노드들 간의 최단 거리를 계산함
            cost = dist + i[1]   # 현재 거리에서 인접 노드 간 가중치를 더함
            
            if cost < distance[i[0]]:   # 기존 해당 노드 간 거리보다 최단값이 나타나면
                distance[i[0]] = cost    # 해당 값으로 교체
                heapq.heappush(q, (cost, i[0]))    # 비용 및 노드 추가
                
    answer = 0

    for i in distance:
        if i<=K:
            answer += 1

    return answer

 

여기서

    for r in road:
        graph[r[0]].append((r[1], r[2]))   # 양방향으로 연결
        graph[r[1]].append((r[0], r[2]))
        
    # ----- 중략
    
    for i in graph[now]:      # 인접한 마을 간 거리 계산
        cost = dist + i[1]   # 현재 거리에서 인접 노드 간 가중치를 더함

        if cost < distance[i[0]]:   # 기존 해당 노드 간 거리보다 최단값이 나타나면
            distance[i[0]] = cost    # 해당 값으로 교체
            heapq.heappush(q, (cost, i[0]))    # 비용 및 노드 추가

 

이 코드를 좀 더 가독성 좋은 코드로 하려면,

	for a, b, cost in road:
            graph[a].append((b, cost))
            graph[b].append((a, cost))
            
    # ----- 중략
    
    for next_node, next_dist in graph[now]:
    	cost = dist + next_dist
        
        if cost < distance[next_node]:
        	distance[next_node] = cost
            heapq.heappush(q, (cost, next_node))

로 개선 가능하다.

 

오늘의 배운점

- 그래프에서 가중치가 양의 정수로 이루어진 그래프에서 최단 거리를 구하고자 할때, 다익스트라 알고리즘을 활용하자.

- 그래프 탐색에서의 최단거리 ==> BFS를 활용하고, visited를 방문여부 및 각 좌표까지의 최단거리를 사용할 배열로 활용

- 영역의 갯수 = DFS 혹은 BFS를 실행한 횟수

- 인덱스, 원소를 함께 활용할 경우 enumerate를 활용하자