#2270

로봇과 그래프

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

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

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

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

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

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

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

#2270

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

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

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

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

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