[경우의 수] 최단경로 문제풀이#2 (실력정석)

최단거리 경우의 수

이 부분이 유형이 다양한데 문제지마다 다 실려있는 게 아니라, 문제풀이 포스팅을 몇 번 더 해볼까 합니다. 가장 기초적인 문제는 아래의 포스팅으로 먼저 풀어보시고, 이 정도는 다 풀 수 있고, 더 추가로 공부하고 싶은 경우에는 오늘 수록한 문제들을 추가로 더 도전해보세요!

 

https://ladyang86.tistory.com/82

[경우의 수] 최단거리 문제풀이 #1 (기본문제)

---

예제1

아래의 그림은 A와 D 사이의 경로를 나타내고 있다.

1. A에서 D로 가는 최단 경로는 모두 몇 가지인지 구하여라.

2. A에서 D로 가는 최단 경로 중 점 B를 지나지 않는 경로는 몇 가지인지 구하여라.

3. A에서 D로 가는 최단 경로 중 점 C를 지나지 않는 경로는 몇 가지인지 구하여라.

---

예제2

아래의 그림과 같은 길이 있다.

1. A에서 PS를 거쳐 B까지 최단 거리로 가는 방법은 몇 가지인지 구하여라.

2. PQ, PR, PS, PT의 네 길이 없을 때, A에서 B까지 최단 거리로 가는 방법은 몇 가지인지 구하여라.

 

sol1) 대각선을 그어서 직접 계산

sol2) 여사건으로 계산

---

예제3.

아래의 그림과 같은 길이 있다.

1. A에서 B까지 최단 거리로 가는 방법은 몇 가지인지 구하여라.

 

sol1) 대각선을 그어서 직접 계산

sol2) 여사건으로 계산

2. A에서 B까지 최단 거리로 가는 길을 잡을 때, C에 도착했을 때에는 D에서, D에 도착했을 때에는 C에서 다시 출발하고, C에서 D, D에서 C로 이동할 때의 방법의 수는 무시한다고 한다. 방법은 몇 가지인지 구하여라.

 

tip : 이 문제는 보통 문제 이해를 못 해서 못 푸는 경우가 많아요. 이건 A부터 B까지의 최단거리를 물어보는 건 동일한데, C와 D 지점은 순간이동을 한다고 생각하시면 됩니다! 즉, 가다가 C에 도착하는 순간 D로 순간이동!!, D에 도착하는 순간에는 C로 순간이동!!해서 다시 B를 향해 간다고 이해하면 됩니다.

 

우선 C,D를 지나지 않는 경우에는 1과 동일하게 대각선으로 다른 지점 잡아서 풀어주면 됩니다.

여기에서 C,D를 지나는 ③,④의 경우만 아래와 같이 수정해주면 되겠죠?

---

예제4

아래의 그림과 같은 길이 있다.

A에서 B까지 최단 거리로 가는 방법은 몇 가지인지 구하여라.

 

tip : 호수가 있는 부분은 어차피 지나갈 수 없는 도로이므로, 먼저 어디를 지날 수 있는지를 파악해주고, 최단으로 가려면 어디를 거쳐 가야하는지를 먼저 파악한 다음 세어줘야 합니다. 

 

그럼 이제 지나갈 수 있는 길의 모양이 확정 되므로, 위에서 썼던 방법 중 편한 걸 이용해서 구해주면 됩니다.

 

sol1) 직접 세기

sol2) 반드시 지나가야 하는 점 파악 후, 경우의 수를 센다.

---

오늘 푼 최단거리 문제는 실력정석에 실려 있는 유제들입니다. 가능하다면 추후 7문제 더 추가로 업로드 해보도록 하겠습니다. 그럼 열심히 공부하시길 :-)