티스토리 뷰
반응형
백준 4485 녹색 옷 입은 애가 젤다지? Python
✅ 문제 소개
문제 내용
젤다의 전설 게임 속 주인공은 **링크**입니다. 그러나 많은 사람들이 “녹색 옷 입은 애가 젤다지?”라고 착각합니다.스트레스를 받은 링크는 도둑루피로 가득한 동굴에 들어갑니다.
링크는 동굴을 통과하며 최대한 적은 루피만 잃고 출구까지 도달해야 합니다.
✅ 테스트케이스
입력 예시
3
5 5 4
3 9 1
3 2 7
0출력 예시
Problem 1: 20✅ 문제 설명
동굴 구조
입력 예시에서 주어진 3×3 동굴입니다.각 칸의 숫자는 해당 칸을 지나갈 때 잃는 루피입니다.
링크는 왼쪽 위(5)에서 출발해 오른쪽 아래(7)로 가야 합니다.
잘못된 경로
**오른쪽 → 오른쪽 → 아래 → 아래** 로만 이동하는 경우입니다.경로: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
손해 합계: **22**
더 좋은 경로
**아래 → 아래 → 오른쪽 → 오른쪽** 로 이동하는 경우입니다.경로: (0,0) → (1,0) → (2,0) → (2,1) → (2,2)
손해 합계: **20**
🔷 문제 풀이 아이디어
이 문제는 링크가 도둑루피가 가득한 동굴을 지나 최소한의 손해로 출구까지 도달하는 것이 목표입니다.단순히 오른쪽과 아래로만 가는 것이 아니라, 더 적은 손해를 위해 **되돌아가 위쪽으로 올라가거나 왼쪽으로 돌아가는 경로**까지 고려해야 합니다.
이 특징 때문에, 단순히 DP로는 풀 수 없고 다익스트라를 써야 합니다.
DP(동적 계획법)의 한계
❌ DP는 현재 위치에서 **오른쪽과 아래만 탐색하며 최소 손해를 계산**합니다.하지만 이 문제처럼 상하좌우 어디든 갈 수 있는 상황에서는 최적 경로를 놓칩니다.
예를 들어, 아래는 DP가 계산한 경로입니다.
모든 칸에는 원래 숫자를 표시하고, 경로를 따라간 칸에는 화살표를 붙였습니다.
🧾 **DP 손해 합계: 20**
다익스트라의 강점
✅ 다익스트라는 이미 방문한 칸이라도 더 적은 손해로 도달할 수 있다면 값을 갱신하며 탐색합니다.상하좌우를 모두 고려하며 최적 경로를 찾기 때문에, 반드시 다익스트라를 사용해야 합니다.
아래는 다익스트라가 계산한 최적 경로입니다.
🧾 **다익스트라 손해 합계: 19**
다익스트라는 무엇인가?
다익스트라는 **가장 적은 비용으로 목적지에 가는 길을 찾는 방법**입니다.원리는 간단합니다.
“지금까지 찾은 길 중에서 제일 싼 길부터 하나씩 확인해 나가면 된다.”
이렇게 하면 큐에서 꺼내는 순간, 그 칸까지 가는 최소 비용이 이미 결정됩니다.
왜냐하면 더 싼 길이 있었으면 그 길이 큐의 맨 앞에 먼저 나왔을 것이기 때문입니다.
이것이 다익스트라가 최소 비용을 보장하는 이유입니다.
다익스트라는 어떻게 움직이는가?
- 1️⃣ 시작점에서 갈 수 있는 칸들의 비용을 계산해 큐에 넣습니다.
- 2️⃣ 큐에서 가장 비용이 적은 칸을 꺼냅니다.
- 3️⃣ 그 칸에서 갈 수 있는 새로운 칸들의 비용을 계산합니다.
- 4️⃣ 더 싸게 갈 수 있으면 그 값을 새로 기록하고 큐에 넣습니다.
- 5️⃣ 이 과정을 반복하면 모든 칸을 최소 비용으로 방문하게 됩니다.
🔷 단계별 진행
🔷 0단계 — 시작
**설명**현재 위치는 `(0,0)`이고, 지금까지 든 비용은 `5`입니다.
갈 수 있는 후보는 오른쪽 `(0,1)=5`와 아래 `(1,0)=3`입니다.
비용 계산:
- 오른쪽: `5+5=10`
- 아래: `5+3=8`
**고유비용**
**설명**
큐에는 `(1,0)=8`과 `(0,1)=10`이 들어 있습니다. 현재 큐의 가장 작은 값은 `8`입니다.
더 싼 길이 있었다면 큐에 먼저 나왔을 텐데 없으니, `(1,0)=8`이 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (1,0)=8 | (0,1)=10 ]←`
다음 탐색 예정: `(1,0)=8`
🔷 1단계 — (1,0)=8 선택
**설명**현재 위치는 `(1,0)`이고, 지금까지 든 비용은 `8`입니다.
갈 수 있는 후보는 아래 `(2,0)=3`과 오른쪽 `(1,1)=9`입니다.
비용 계산:
- 아래: `8+3=11`
- 오른쪽: `8+9=17`
**고유비용**
**설명**
큐에는 기존의 `(0,1)=10`, 그리고 새로 발견한 `(2,0)=11`, `(1,1)=17`이 있습니다.
가장 작은 값은 여전히 `10`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로 `10`이 최소입니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (0,1)=10 | (2,0)=11 | (1,1)=17 ]←`
다음 탐색 예정: `(0,1)=10`
🔷 2단계 — (0,1)=10 선택
**설명**현재 위치는 `(0,1)`이고, 지금까지 든 비용은 `10`입니다.
갈 수 있는 후보는 오른쪽 `(0,2)=4`와 아래 `(1,1)=9`입니다.
비용 계산:
- 오른쪽: `10+4=14`
- 아래: `10+9=19`
**고유비용**
**설명**
큐에는 기존의 `(2,0)=11`, `(1,1)=17`, 그리고 새로 발견한 `(0,2)=14`가 있습니다.
가장 작은 값은 `11`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로 `11`이 최소입니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (2,0)=11 | (1,1)=17 | (0,2)=14 ]←`
다음 탐색 예정: `(2,0)=11`
🔷 3단계 — (2,0)=11 선택
**설명**현재 위치는 `(2,0)`이고, 지금까지 든 비용은 `11`입니다.
갈 수 있는 후보는 오른쪽 `(2,1)=2`입니다.
비용 계산:
- 오른쪽: `11+2=13`
**고유비용**
**설명**
큐에는 기존의 `(1,1)=17`, `(0,2)=14`가 있습니다.
새롭게 발견한 `(2,1)=13`이 추가되었습니다.
큐를 보면 `13`, `14`, `17`이 있고, 가장 작은 값은 `13`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(2,1)=13`이 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (2,1)=13 | (0,2)=14 | (1,1)=17 ]←`
다음 탐색 예정: `(2,1)=13`
🔷 4단계 — (2,1)=13 선택
**설명**현재 위치는 `(2,1)`이고, 지금까지 든 비용은 `13`입니다.
갈 수 있는 후보는 오른쪽 `(2,2)=7`입니다.
비용 계산:
- 오른쪽: `13+7=20`
**고유비용**
**설명**
큐에는 기존의 `(0,2)=14`, `(1,1)=17`이 있습니다.
새롭게 발견한 `(2,2)=20`이 추가되었습니다.
큐를 보면 `14`, `17`, `20`이 있고, 가장 작은 값은 `14`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(0,2)=14`가 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (0,2)=14 | (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(0,2)=14`
🔷 다익스트라 — 단계별 진행 (완결)
🔷 5단계 — (0,2)=14 선택
**설명**현재 위치는 `(0,2)`이고, 지금까지 든 비용은 `14`입니다.
갈 수 있는 후보는 아래 `(1,2)=1`입니다.
비용 계산:
- 아래: `14+1=15`
**고유비용**
**설명**
큐에는 기존의 `(1,1)=17`, `(2,2)=20`이 있습니다.
새롭게 발견한 `(1,2)=15`이 추가되었습니다.
큐를 보면 `15`, `17`, `20`이 있고, 가장 작은 값은 `15`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(1,2)=15`가 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (1,2)=15 | (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(1,2)=15`
🔷 6단계 — (1,2)=15 선택
**설명**현재 위치는 `(1,2)`이고, 지금까지 든 비용은 `15`입니다.
갈 수 있는 후보는 아래 `(2,2)=7`입니다.
비용 계산:
- 아래: `15+7=22`
**고유비용**
**설명**
큐에는 기존의 `(1,1)=17`, `(2,2)=20`이 있습니다.
가장 작은 값은 `17`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(1,1)=17`이 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(1,1)=17`
🔷 7단계 — (1,1)=17 선택
**설명**현재 위치는 `(1,1)`이고, 지금까지 든 비용은 `17`입니다.
갈 수 있는 후보는 아래 `(2,1)=2`와 오른쪽 `(1,2)=1`입니다.
하지만 `(2,1)=13`과 `(1,2)=15`가 이미 더 작은 비용으로 기록돼 있으므로, 아무것도 갱신되지 않습니다.
**고유비용**
**설명**
큐에는 이제 `(2,2)=20`만 남아 있습니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(2,2)=20`이 최소임이 보장됩니다.
**합산비용**
**설명**
현재 큐 상태: `←[ (2,2)=20 ]←`
다음 탐색 예정: `(2,2)=20`
🔷 8단계 — (2,2)=20 선택
**설명**현재 위치는 `(2,2)`이고, 지금까지 든 비용은 `20`입니다.
목적지에 도달했으므로 탐색을 종료합니다.
**고유비용**
**설명**
이제 큐가 비었고, 목적지까지 최소 비용 `20`으로 도달했습니다.
이 과정에서 매 단계마다 큐에서 가장 작은 값부터 탐색했고, 더 싼 길이 있었다면 그 순간 큐에 나타났을 것이므로 최소임이 증명됩니다.
**합산비용**
**설명**
최종 최소 비용: `20`
전체코드
from queue import PriorityQueue
class Node:
def __init__(self,x,y,cost):
self.x=x
self.y=y
self.cost=cost
def __lt__(self,other):
return self.cost<other.cost
dx=[-1,1,0,0]
dy=[0,0,-1,1]
cnt =0
while True:
N= int(input())
if N==0:
break
cnt+=1
arr = [[0 for _ in range(N)] for _ in range(N)]
dis = [[21000000 for _ in range(N)] for _ in range(N)]
for i in range(N):
row=list(map(int,input().split()))
for j in range(N):
arr[i][j]=row[j]
q=PriorityQueue()
node=Node(0,0,arr[0][0])
q.put(node)
dis[0][0]=arr[0][0]
while not q.empty():
node = q.get()
x = node.x
y = node.y
cost = node.cost
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=N or ny<0 or ny>=N:
continue
next_cost=cost+arr[nx][ny]
if(next_cost<dis[nx][ny]):
dis[nx][ny]=next_cost
q.put(Node(nx,ny,next_cost))
print(f'Problem {cnt}: {dis[N-1][N-1]}')개별 코드 설명 및 보강
1. class Node
class Node:
def __init__(self,x,y,cost):
self.x=x
self.y=y
self.cost=cost
def __lt__(self,other):
return self.cost<other.cost- `Node` 클래스는 탐색 대상인 2차원 배열 내 위치를 나타내는 좌표 `(x, y)`와, 그 위치까지 도달하는 데 필요한 누적 비용 `cost`를 저장합니다.
- 이 클래스를 우선순위 큐에 넣어 최소 비용부터 처리하기 위해 `__lt__` (less than) 매직 메서드를 오버로딩하였습니다.
- 오버로딩된 `__lt__` 메서드는 `self.cost < other.cost` 형태로 구현하여, **비용이 작은 노드가 우선순위 큐에서 먼저 나오도록** 작동합니다.
- 이렇게 하면 Python의 `PriorityQueue`가 기본적으로 최소힙(min-heap)으로 동작하여, 항상 가장 비용이 적은 노드를 먼저 처리할 수 있습니다.
2. 배열 선언 및 초기화
arr = [[0 for _ in range(N)] for _ in range(N)]
dis = [[21000000 for _ in range(N)] for _ in range(N)]- `arr` 배열은 각 칸마다 존재하는 개별 비용(도둑루피 크기)을 저장하는 2차원 리스트입니다.
- 입력값으로 초기화되며, 탐색 대상 동굴의 구조와 비용을 나타냅니다.
- `dis` 배열은 현재까지 발견한 해당 칸까지 도달하는 **최소 누적 비용**을 저장합니다. 초기값은 매우 큰 수(21000000)로 설정하여, 어떤 경로든 초기값보다 작게 되도록 합니다. 이는 무한대 값을 의미합니다.
- 탐색 진행 중에 지속적으로 갱신되며, 최종적으로 출구까지 도달하는 최소 비용을 찾는 데 사용됩니다.
3. 초기 설정 및 탐색 시작
q=PriorityQueue()
node=Node(0,0,arr[0][0])
q.put(node)
dis[0][0]=arr[0][0]- `PriorityQueue` 객체를 생성하여 다익스트라 알고리즘에 사용할 우선순위 큐를 준비합니다.
- 출발 지점인 `(0,0)` 위치의 비용 `arr[0][0]`을 포함하는 `Node` 객체를 생성합니다.
- 이 `Node`를 큐에 넣어 탐색을 시작할 준비를 합니다.
- `dis[0][0]`에도 출발 지점의 비용을 초기화하여, 이 값이 시작점의 최소 비용임을 명시합니다.
4. 큐가 빌 때까지 반복
while not q.empty():- 큐가 비어있다는 것은, 탐색해야 할 후보 위치가 더 이상 없음을 뜻합니다.
- 즉, 모든 가능한 경로를 확인했고, 최소 비용 경로를 찾았다는 의미입니다.
- 따라서 이 반복문은 아직 탐색할 노드가 남아 있는 동안 계속 실행됩니다.
5. 현재 최소 비용 노드 꺼내기
node = q.get()
x = node.x
y = node.y
cost = node.cost- 큐의 맨 위에 있는 노드를 꺼내 현재 위치 `(x, y)`와 그 위치까지 도달하는 **누적 비용 `cost`**를 가져옵니다.
- 이 노드는 지금까지 발견한 경로 중 비용이 가장 적은 위치를 의미합니다.
- 큐에서 꺼낸 후, 그 위치를 기준으로 다음 위치 탐색을 진행합니다.
6. 상하좌우 4방향 탐색 및 유효성 검사
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=N or ny<0 or ny>=N:
continue- 현재 위치에서 상하좌우 네 방향을 모두 탐색하기 위해 반복문을 사용합니다. `dx`와 `dy` 리스트를 활용하여 각 방향으로 이동한 새 좌표 `(nx, ny)`를 계산합니다.
- 이동한 위치가 배열(`N x N` 그리드)의 범위를 벗어나면, 유효하지 않은 좌표이므로 탐색하지 않고 건너뜁니다.
- 이렇게 범위를 벗어나는 경우를 사전에 걸러내어, 불필요한 오류와 탐색을 막습니다.
7. 다음 위치의 누적 비용 계산
next_cost=cost+arr[nx][ny]- 다음 위치 `(nx, ny)`까지 도달하는 데 드는 누적 비용을 계산합니다.
- 현재 위치까지의 누적 비용 `cost`에 다음 위치의 개별 비용 `arr[nx][ny]`를 더합니다.
- 이 값은 다음 위치까지 가는 경로의 새로운 비용 후보가 됩니다.
8. 더 적은 비용으로 갱신 및 큐에 추가
if(next_cost<dis[nx][ny]):
dis[nx][ny]=next_cost
q.put(Node(nx,ny,next_cost))- 만약 계산한 `next_cost`가 현재 `dis` 배열에 기록된 `(nx, ny)`까지의 최소 비용(`dis[nx][ny]`)보다 작다면,
- 해당 위치까지 도달하는 최소 비용을 `next_cost`로 갱신합니다.
- 그리고 이 `(nx, ny)` 위치를 포함하는 새로운 `Node`를 우선순위 큐에 추가하여, 추후에 이 위치를 기준으로 더 나은 경로를 탐색할 기회를 만듭니다.
- 이 과정이 다익스트라 알고리즘의 핵심으로, 이미 방문한 위치라도 더 좋은 비용으로 도달 가능하다면 갱신하고 재탐색하는 방식입니다.
결론
- 이 알고리즘은 단순히 한 번 방문한 칸을 다시 방문하지 않는 것이 아니라,
- 더 낮은 비용으로 해당 칸에 도달할 수 있으면, 비용을 갱신하고 다시 큐에 넣어 더 나은 경로를 찾아가는 **유연한 탐색 방식**입니다.
- 우선순위 큐가 최소 비용 노드를 먼저 꺼내 처리하기 때문에, 항상 비용이 작은 경로부터 확정해 나가면서 효율적으로 최소 비용 경로를 찾습니다.
- 이 점이 다익스트라 알고리즘의 본질이며, 그리디한 접근임에도 전체 경로 최적해를 보장하는 이유입니다.
반응형
'백준 스터디' 카테고리의 다른 글
| 백준 1026번 보물 Python 풀이 (1) | 2025.07.19 |
|---|---|
| 백준 1026번 보물 C++ 풀이 (0) | 2025.07.19 |
| 백준 4485 녹색 옷 입은 애가 젤다지? C++ 풀이 (0) | 2025.07.18 |
| 백준 24416번: 알고리즘 수업 - 피보나치 수 1 (C++) (0) | 2025.07.16 |
| 백준 24416번: 알고리즘 수업 - 피보나치 수 1 (Python) (1) | 2025.07.16 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그리디알고리즘
- 파이썬코딩
- 그래프 탐색
- 브루트포스
- 프로그래머스
- DP
- 문자열처리
- 동적계획법
- 알고리즘
- 백준
- 알고리즘기초
- 코딩 테스트
- HTML
- 알고리즘문제풀이
- 파이썬
- C++
- 상속
- python 알고리즘
- Python
- 코딩테스트
- 프로그래밍
- 그리디
- 동적 계획법
- dfs
- 문제 풀이
- 코딩
- 알고리즘 문제풀이
- 객체지향
- 문제풀이
- c언어
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 30 |
글 보관함
반응형