도전 과제 : 길 찾기

본 자료는 인공지능을 활용하지 않고 작성되었음을 알립니다.

첫번째 질문

한 도시에 아래와 같이 도로가 연결되어 있는 두 지점 $A$와 $B$가 있다. $A$에서 $B$로 가는 최단 경로의 개수는 몇 개일까?

두번째 질문

이번에는 $P$로 나타내어진 사거리가 공사 중이라, 이를 피해서 가야 한다고 한다. 이번에는 $A$에서 $B$로 가는 최단 경로의 개수는 몇 개일까?

세번째 질문

일주일 뒤, 공사는 마무리 단계에 접어들었다. 이제는 $P$를 지날 수는 있으나, 직진이나 좌회전은 불가능하고 우회전만이 가능하다. $A$에서 $B$로 가는 최단 경로의 개수는 몇 개일까?

네번째 질문

첫번째 질문의 상황을 일반화해보자. 세로로 $M$개, 가로로 $N$개의 블럭이 있는 직사각형 모양의 도시를 생각하자. 꼭짓점 $A$에서 반대편 꼭짓점 $B$로 가는 최단 경로의 개수는 몇 개인가?

다섯번째 질문

두번째 질문의 상황을 일반화해보자. 세로로 $M$개, 가로로 $N$개의 블럭이 있는 직사각형 모양의 도시에서, 점 $P=\rm(x,y)$는 지날 수 없다고 한다. 꼭짓점 $A$에서 반대편 꼭짓점 $B$로 가는 최단 경로의 개수는 몇 개인가?

여섯 번째 질문

세번째 질문의 상황을 일반화해보자. 아래와 같은 상황에서 점 $P$에서 우회전만이 가능할 때, 꼭짓점 $A$에서 반대편 꼭짓점 $B$로 가는 최단 경로의 개수는 몇 개인가?

최종 보스 : HW

아래와 같이 가로 방향으로 $N$개, 세로 방향으로 $2$개의 원이 놓여 있는 상황을 생각해보자. 점 $A$에서 출발하여 원들을 따라 점 $B$로 가는 최단 경로의 개수를 구하시오. (단, 점 $A$와 점 $B$는 각 점이 속해 있는 원의 중심과 높이가 같다)