#2270

로봇과 그래프

위와 같은 방향 그래프가 있다. 어떤 로봇이 정점 A에 놓여 있으며, 정점 X에 도착하는 것이 목표이다.

빨간색 간선들은 왼쪽에서 오른쪽으로 향하며, 실선 형태 (→)로 표시되어 있다. 파란색 간선들은 A ⇠ A 간선을 제외하고는 오른쪽에서 왼쪽으로 향하며, 점선 형태 (⇠)로 표시되어 있다.

X를 제외한 모든 정점에는 해당 정점에서 출발하는 빨간색 간선과 파란색 간선이 정확히 하나씩 있다.

이때, 로봇은 아래와 같은 방식으로 그래프를 돌아다닐 것이다.

예를 들어 처음 몇 번의 이동 과정에서 방문하는 정점들을 정점(방문 횟수) 형태로 순서대로 표현하면 다음과 같다: A(1) ⇢ A(2) → B(1) ⇢ A(3) ⇢ A(4) → B(2) → C(1) ⇢ B(3) ⇢ …

로봇은 정점 X에 도착할 때까지 총 몇 번 이동하는가? (이동 횟수는 간선을 지나간 총 횟수임에 유의하라.)

문제를 해결하려면 로그인해 주세요.