TIL 코딩공장

백준 파이썬 공부 2025.11.02
1167번 트리의 지름 (골드 2)

1. 문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 
트리의 지름을 구하는 프로그램을 작성하시오.

2. 입력
트리가 입력으로 주어진다. 
먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)
둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 
정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 
하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 
예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 
정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 
각 줄의 마지막에는 -1이 입력으로 주어진다. 
주어지는 거리는 모두 10,000 이하의 자연수이다.

3. 출력
첫째 줄에 트리의 지름을 출력한다.

4. 문제 풀이
전에 풀었던 1967번 트리의 지름과 동일한 문제인데, 간선과 가중치가 입력되는 방식만 다른 문제이다.
트리의 지름을 구하는 방식은 동일하게
아무 노드에서 가장 먼 노드 A를 구하고, A에서 가장 먼 노드 B를 찾아 A,B 사이의 거리를 구하면 된다.
가장 먼 곳의 거리를 구하는 방식은 BFS를 사용하면 된다.

>>>코드

"""
1167번 트리의 지름
입력 : n (노드의 개수)  
parent, child, w -1 (간선정보: 부모노드, 자식노드, 가중치)
출력 : diameter (트리의 지름)
>> 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
"""
from collections import deque

n = int(input())
line = [[] for _ in range(n+1)]
for i in range(n):
    data = list(map(int, input().split()))
    parent = data[0]
    idx = 1
    while data[idx] != -1:
        child, w = data[idx], data[idx+1]
        line[parent].append((child, w))
        idx += 2

def tree_dist(start):
    queue = deque()
    queue.append(start)
    
    dist = [-1] * (n+1)
    dist[start] = 0
    while queue:
        cur = queue.popleft()
        
        for next_node, w in line[cur]:
            if dist[next_node] == -1:
                dist[next_node] = dist[cur] + w
                queue.append(next_node)
    
    far_node = dist.index(max(dist))
    return far_node, max(dist)

a, _ = tree_dist(1)
_, diameter = tree_dist(a)
print(diameter)

5. 문제 링크
https://www.acmicpc.net/problem/1167

백준 파이썬 공부 2025.11.01
2206번 벽 부수고 이동하기 (골드 3)

1. 문제
N×M의 행렬로 표현되는 맵이 있다. 
맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 
당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 
최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 
이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 
벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

2. 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 
다음 N개의 줄에 M개의 숫자로 맵이 주어진다. 
(1, 1)과 (N, M)은 항상 0이라고 가정하자.

3. 출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

4. 문제 풀이
일단 격자 그래프에서 최단거리를 구하는 문제이기에, BFS를 사용하면 된다.
다만 변형이 들어간 것이, 벽을 하나까지 허물 수 있다는 것.
처음에는 브루트 포스로 모든 경우의 MAP을 적용시켜 최단거리를 구해야하나 했지만,
그렇게 하면, 시간도 메모리도 너무 많이 사용되기에 그럴리가 없다.

해결책은 visited 리스트를 3차원으로 만들어, 이동횟수를 저장하는 것이다.

< (n x m x 2) visited 리스트 >
- 벽을 허물지 않은 경우는 visited[x][y][0]에 이동횟수 저장
- 벽을 허문 경우는 visited[x][y][1]에 이동횟수를 저장

어디에서 벽을 허물든 애초에 가장 빠르게 (n,m)에 도착한 경우만 알면 되므로,
queue를 이용한 BFS 로 해결 가능하다.

>>>코드

"""
2206번 벽 부수고 이동하기
입력 : n, m (맵의 높이와 너비)  
MAP (맵 정보: 0 = 길, 1 = 벽)
출력 : min_dist (최단거리)
>> (1,1)에서 (n,m)까지의 최단거리
>> 벽을 하나까지 부수는 것이 가능
"""
from collections import deque

n, m = map(int, input().split())
MAP = [list(map(int, input())) for _ in range(n)]

def BFS():
    visited = [[[0] * 2 for i in range(m)] for j in range(n)]
    visited[0][0][0] = 1
    
    queue = deque()
    queue.append((0, 0, 0))
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        x, y, z = queue.popleft()
    
        if x == n-1 and y == m-1:
            return visited[x][y][z]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m:
                # 다음 이동할 곳이 벽이고, 벽파괴기회를 사용하지 않은 경우
                if MAP[nx][ny] == 1 and z == 0 :
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append((nx, ny, 1))
                # 다음 이동할 곳이 벽이 아니고, 아직 한 번도 방문하지 않은 곳이면
                elif MAP[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append((nx, ny, z))
    return -1
 
print(BFS())

5. 문제 링크
https://www.acmicpc.net/problem/2206

백준 파이썬 공부 2025.10.31
1967번 트리의 지름 (골드 4)

1. 문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 
트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 
트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 
이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 
정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 
트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 
아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

2. 입력
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 
둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 
간선에 대한 정보는 세 개의 정수로 이루어져 있다. 
첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 
두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 
간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 
부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 
루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

3. 출력
첫째 줄에 트리의 지름을 출력한다.

4. 문제 풀이
트리라고 해서 뭔가 어려워보이고, 구현해야하나 싶지만, 트리의 성질만 알고 있으면 비교적 간단한 문제.
일단 처음에는 간선이 있고, 가중치가 있는데, 최대 거리를 구하는 것이기에
최대힙을 통해 최대거리를 구하는 방식으로 문제를 풀자고 생각했다.

그리고 알아야 하는 기본 개념들이 존재한다.
- 트리의 성질 1. 간선의 개수는 노드의 개수 -1 이다.

>>>코드1. 메모리 초과

"""
1967번 트리의 지름
입력 : n (노드의 개수)  
parent, child, w (간선정보: 부모노드, 자식노드, 가중치)
출력 : diameter (트리의 지름)
>> 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
>> 가중치 있는 최대거리 == 최대 힙 이용한 다익스트라 변형
"""
import heapq

n = int(input())
line = [[] for _ in range(n+1)]
for i in range(n-1):
    parent, child, w = map(int, input().split())
    line[parent].append((child, w))
    line[child].append((parent, w))

def tree_diameter():
    diameter = 0
    
    for start in range(1, n+1):
        maxheap = []
        heapq.heappush(maxheap, (0, start))
        
        dist = [0] * (n+1)
        while maxheap:
            cur_dist, cur = heapq.heappop(maxheap)
            cur_dist = -cur_dist
            
            if cur_dist < dist[cur]:
                continue
            
            for next_node, w in line[cur]:
                if dist[next_node] < cur_dist + w:
                    dist[next_node] = cur_dist + w
                    heapq.heappush(maxheap, (-dist[next_node], next_node))
                    
        diameter = max(diameter, max(dist))
    return diameter
        
print(tree_diameter())

아마도 모든 노드에서 다익스트라 알고리즘을 적용시켜서 일어나는 일 같다.
A에서 가장 먼 곳의 노드 B를 찾고 B와 가장 먼곳의 노드 C를 찾으면,
트리의 지름은 B와 C의 거리이다.
말만 들으면 이상하게 들릴 수도 있다. 
??? : 아니 A 에서 가장 먼곳 B와 B에서 가장 먼곳 C면 지름 A - C 아님??
아닙니다... 일단은 지름이 A-C였으면 애초에 A에서 가장 먼 곳이 C였을 거다...

이게 일반적인 길찾기랑은 다르다.
- 트리의 경우 각각의 노드 사이의 간선이 한가지만 존재하며, 사이클(회전)이 없기 때문에,
A노드에서 B노드로 가는 길은 한가지 밖에 존재하지 않는다.
- 따라서 트리 내의 어느 노드에서든, 가장 먼 곳의 노드는 트리 지름의 한쪽을 맡는 노드이다.
- 그리고 한 트리 지름에서 가장 먼 곳은 트리 지름의 반대편 노드이다.

- 트리의 성질 2: A에서 가장 먼 곳의 노드 B, B와 가장 먼곳의 노드 C가 있다면 트리의 지름은 B와 C의 거리이다.

>>코드2. 다익스트라 이용 : 메모리 초과

"""
1967번 트리의 지름
입력 : n (노드의 개수)  
parent, child, w (간선정보: 부모노드, 자식노드, 가중치)
출력 : diameter (트리의 지름)
>> 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
>> 가중치 있는 최대거리 == 최대 힙 이용한 다익스트라 변형
"""
import heapq

n = int(input())
line = [[] for _ in range(n+1)]
for i in range(n-1):
    parent, child, w = map(int, input().split())
    line[parent].append((child, w))
    line[child].append((parent, w))

def tree_dist(start):
    maxheap = []
    heapq.heappush(maxheap, (0, start))
    
    dist = [0] * (n+1)
    while maxheap:
        cur_dist, cur = heapq.heappop(maxheap)
        cur_dist = -cur_dist
        
        if cur_dist < dist[cur]:
            continue
        
        for next_node, w in line[cur]:
            if dist[next_node] < cur_dist + w:
                dist[next_node] = cur_dist + w
                heapq.heappush(maxheap, (-dist[next_node], next_node))
    
    far_node = dist.index(max(dist))
    return far_node, max(dist)

a, _ = tree_dist(1)
_, diameter = tree_dist(a)
print(diameter)

근데 사실 다익스트라가 없어도 된다. 그걸 코드를 고치면서 깨달았다.
단순히 음수인 가중치가 없는 상황에서 최대거리를 구하는 방식은 BFS로도 구할 수 있다.
애초에 경로의 경우의 수가 1개인데 다익스트라를 사용할 이유가 없다....

>>코드3. BFS 이용 : 정답입니다.

"""
1967번 트리의 지름
입력 : n (노드의 개수)  
parent, child, w (간선정보: 부모노드, 자식노드, 가중치)
출력 : diameter (트리의 지름)
>> 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
"""
from collections import deque

n = int(input())
line = [[] for _ in range(n+1)]
for i in range(n-1):
    parent, child, w = map(int, input().split())
    line[parent].append((child, w))
    line[child].append((parent, w))

def tree_dist(start):
    queue = deque()
    queue.append(start)
    
    dist = [-1] * (n+1)
    dist[start] = 0
    while queue:
        cur = queue.popleft()
        
        for next_node, w in line[cur]:
            if dist[next_node] == -1:
                dist[next_node] = dist[cur] + w
                queue.append(next_node)
    
    far_node = dist.index(max(dist))
    return far_node, max(dist)

a, _ = tree_dist(1)
_, diameter = tree_dist(a)
print(diameter)

코드자체는 간단한데, 트리의 성질, 경로의 특성, 트리의 지름의 특성을 이해해야 되는 문제이다.

이래서 자료구조랑 알고리즘 개념과 특성을 제대로 공부해야 한다.

5. 문제 링크
https://www.acmicpc.net/problem/1967

백준 파이썬 공부 2025.10.30
11404번 플로이드 (골드 4)

1. 문제
n(2 ≤ n ≤ 100)개의 도시가 있다. 
그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 
각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 
그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 
먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 
버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 
시작 도시와 도착 도시가 같은 경우는 없다. 
비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

3. 출력
n개의 줄을 출력해야 한다. 
i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 
만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

4. 문제 풀이
가중치가 있는 최소 거리 해결 문제이므로 다익스트라 알고리즘을 사용한다

>>>코드

"""
11404번 플로이드
입력 : n (도시 수), m (버스 수)  
bus (버스의 정보: 출발지, 도착지, 비용)
출력 : min_dist (i에서 j로 가는 최소 비용)
>> 경로가 존재하지 않는 경우 0 출력
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, w = map(int, input().split())
    bus[s].append((e, w))
    
def min_dist(start):
    heap = []
    heapq.heappush(heap, (0, start))
    
    dist = [float('inf')] * (n+1)
    dist[start] = 0
    
    while heap:
        cur_dist, cur = heapq.heappop(heap)
        
        if cur_dist > dist[cur]:
            continue
        
        for next_station, w in bus[cur]:
            if dist[next_station] > cur_dist + w:
                dist[next_station] = cur_dist + w
                heapq.heappush(heap, (dist[next_station], next_station))
    
    return dist
        
for i in range(1, n+1):
    distance = min_dist(i)
    for j in range(1, n+1):
        if distance[j] == float('inf'):
            print(0, end = " ")
        else:
            print(distance[j], end = " ")
    print()

5. 문제 링크
https://www.acmicpc.net/problem/11404

백준 파이썬 공부 2025.10.29
9935번 문자열 폭발 (골드 4)

1. 문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 
폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 
남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 
남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

2. 입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

3. 출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

4. 문제 풀이
괄호문제랑 비슷해보이면서 다르다. 
괄호 검사의 경우 왼쪽 괄호가 나오면 push, 오른쪽 괄호가 나오면 pop을 하는 방식으로 했는데, 
이건 bomb 문자열 외에도 일반 문자열이 존재하며, bomb문자열이 붙어있어야만 제거가 가능하기 때문

따라서 stack을 이용하되, 
검사를 할때, push된 문자열을 기준으로 마지막에 bomb 문자열이 존재한다면 pop하는 방식으로 코드를 작성한다.

>>코드

"""
9953번 문자열 폭발
입력 : arr (전체 문자열)  
bomb (폭탄 문자열)
출력 : survive (살아남은 문자열)
>> 전부 삭제될 경우 FRULA 출력
>> 일단 스택에 추가 후, 스택 마지막에 폭탄문자열이 있다면 pop(del)
"""
arr = input().rstrip()
bomb = input().rstrip()

stack = []
lenB = len(bomb)
for c in arr:
    stack.append(c)
    if len(stack) >= lenB:
        if ''.join(stack[-lenB:]) == bomb:
            del stack[-lenB:]

if stack:
    print(''.join(stack))
else:
    print("FRULA")

5. 문제 링크
https://www.acmicpc.net/problem/9935

백준 파이썬 공부 2025.10.28
1753번 최단경로 (골드 4)

1. 문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 
단, 모든 간선의 가중치는 10 이하의 자연수이다.

2. 입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 
모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 

둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 

셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 
이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. 
u와 v는 서로 다르며 w는 10 이하의 자연수이다. 
서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

3. 출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 
시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

4. 문제 풀이
가중치를 가진 경로의 최단거리 이므로 최소힙을 이용한 다익스트라 알고리즘으로 문제를 풀이한다

>>코드

"""
1753번 특정한 최단 경로
입력 : v (정점 수), e (간선 수)  
k (시작정점)
a(간선 시작점), b (간선 도착점) c (가중치)
출력 : min_dist (최단 경로 길이)
>> 시작 정점 k로부터 모든 정점까지의 최단거리
"""
import heapq

v, e = map(int, input().split())
k = int(input())
path = list([] for _ in range(v+1))
for _ in range(e):
    a, b, c = map(int, input().split())
    path[a].append((b, c))

def min_dist(start):
    dist = [float('inf')] * (v+1)
    dist[start] = 0
    
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        cur_dist, cur = heapq.heappop(heap)
        
        if cur_dist > dist[cur]:
            continue
        
        for next_node, w in path[cur]:
            if dist[next_node] > cur_dist + w:
                dist[next_node] = cur_dist + w
                heapq.heappush(heap, (dist[next_node], next_node))
    
    return dist

result = min_dist(k)
for i in range(1, len(result)):
    if result[i] == float('inf'):
        print("INF")
    else:
        print(result[i])

5. 문제 링크
https://www.acmicpc.net/problem/1753

백준 파이썬 공부 2025.10.27
1504번 특정한 최단 경로 (골드 4)

1. 문제
방향성이 없는 그래프가 주어진다. 
세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 
또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 
그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 
하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 
1번 정점에서 N번 정점으로 이동할 때, 
주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 

둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, 
a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 

다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 
임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

3. 출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 
그러한 경로가 없을 때에는 -1을 출력한다.

4. 문제 풀이
해당 문제는 가중치가 있는 그래프의 최단경로 문제이므로,
다익스트라(Dijkstra) 알고리즘으로 풀어야 한다.
다익스트라 알고리즘은 
1. 출발노드를 기준으로 각 노드의 최소비용을 저장
2. 방문하지 않은 노드 중 가장 비용이 적은 노드부터 이동
3. 만약 해당 경로를 통해 도착한 노드까지의 비용이 저장된 최소비용보다 작을 경우 최소비용 갱신
4. 2,3번 반복

- 간선 정보 저장 : 각각의 노드 번호의 인덱스에 연결 간선과 길이를 튜플로 저장
- 다익스트라 알고리즘 : 최소큐를 통해 저장된 경로들 중 가장 짧은 (가까운) 경로의 노드부터 탐색
- 노드 최단거리 저장 : 리스트에 float('inf') X (n+1) 로 각각의 노드까지의 거리 초기화

>>>코드

"""
1504번 특정한 최단 경로
입력 : n (정점 수), e (간선 수)  
a, b (연결된 정점) c (두 정점 사이 거리)
v1, v2 (반드시 거쳐야하는 정점 2개)
출력 : min_dist (최단 경로 길이)
>> 1번 정점에서 v1, v2 정점을 거쳐 n번 정점까지 도달하는 최단거리
"""
import heapq

n, e = map(int, input().split())
path = list([] for _ in range(n+1))
for _ in range(e):
    a, b, c = map(int, input().split())
    path[a].append((b, c))
    path[b].append((a, c))
    
v1, v2 = map(int, input().split())

def min_dist(start, end):
    dist = [float('inf')] * (n+1)
    dist[start] = 0
    
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        cur_dist, cur = heapq.heappop(heap)
        
        if cur_dist > dist[cur]:
            continue
        
        for next_node, w in path[cur]:
            if dist[next_node] > cur_dist + w:
                dist[next_node] = cur_dist + w
                heapq.heappush(heap, (dist[next_node], next_node))
    
    return dist[end]
            
# 경로 1 : 1 > v1 > v2 > n
path1 = min_dist(1, v1) + min_dist(v1, v2) + min_dist(v2, n)
# 경로 2 : 1 > v2 > v1 > n
path2 = min_dist(1, v2) + min_dist(v2, v1) + min_dist(v1, n)

answer = min(path1, path2)
if answer == float('inf'):
    print(-1)
else:
    print(answer)

5. 문제 링크
https://www.acmicpc.net/problem/1504

백준 파이썬 공부 2025.10.26
15686번 치킨 배달 (골드 5)

1. 문제
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 
도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 
도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. 
r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 
따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 
치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 
즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 
도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, 
(5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 
따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, 
(5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 
따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 
프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 
오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 
어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 
집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 
치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

3. 출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 
도시의 치킨 거리의 최솟값을 출력한다.

4. 문제 풀이
현재 존재하는 치킨집 중 m의 크기를 가진 부분 집합의 조합을 모두 고려해보는 문제이다.
모든 조합을 확인하는 방법으로, 재귀와 백트래킹을 이용하여 해당 방식을 구현한다.

>>코드1. 재귀와 백트래킹 이용

"""
15686번 치킨 배달
입력 : n (도시 가로세로 길이), m (최대 치킨집 수)  
city (도시의 상태 : 0 빈칸, 1 집, 2 치킨집)
출력 : min_chicken (도시의 치킨거리 최소값)
>> 치킨거리 = 집과 가장 가까운 치킨집의 거리
>> 도시의 치킨거리 = 모든 집의 치킨거리의 합
"""
n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
min_distance = float('inf')
chicken, house, restruct = [], [], []

def calculate():
    result = 0
    for i, j in house:
        distance = float('inf') 
        for k, l in restruct:
            distance = min(distance, abs(i-k) + abs(j-l))
        result += distance
    return result

def reduce(cur, cnt):
    global min_distance
    if cnt == m:
        min_distance = min(min_distance, calculate())
        return
    if cur >= len(chicken):
        return
    
    restruct.append(chicken[cur])
    reduce(cur+1, cnt+1)
    restruct.pop()
    reduce(cur+1, cnt)
    
for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chicken.append([i, j])
        elif city[i][j] == 1:
            house.append([i, j])

reduce(0, 0)
print(min_distance)

   

다만, 파이썬 itertools 라이브러리에는 조합을 찾아주는 함수가 존재한다.
이를 이용하면 모든 조합을 구현하지 않고 바로 생성이 가능하다.
import itertools
ltertools.combinations(전체집합, 부분집합의크기)

>>코드2. itertools 라이브러리 이용

"""
15686번 치킨 배달
입력 : n (도시 가로세로 길이), m (최대 치킨집 수)  
city (도시의 상태 : 0 빈칸, 1 집, 2 치킨집)
출력 : min_chicken (도시의 치킨거리 최소값)
>> 치킨거리 = 집과 가장 가까운 치킨집의 거리
>> 도시의 치킨거리 = 모든 집의 치킨거리의 합
"""
import itertools
n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
min_distance = float('inf')
chicken, house, restruct = [], [], []

for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chicken.append([i, j])
        elif city[i][j] == 1:
            house.append([i, j])

# 치킨집들 중 m개를 고르는 조합에 대한 모든 경우의 수
restruct = list(itertools.combinations(chicken, m))

def calculate():
    min_dist = float('inf')
    for KFC in restruct:
        tot_dist = 0
        for customer in house:
            dist = float('inf') 
            for i in range(m):
                dist = min(dist, abs(customer[0]-KFC[i][0]) + abs(customer[1]-KFC[i][1]))
            tot_dist += dist
        min_dist = min(min_dist, tot_dist)
    
    return min_dist

print(calculate())

5. 문제 링크
https://www.acmicpc.net/problem/15686