섬을 만들고 꾸미는 스마트폰 게임을 하던 은주와 세영이는
인접한 섬들 사이에 다리를 놓아 모든 섬을 연결 했습니다.
하지만 황금이 모자라서 무정한 다리를 많이 놓을수는 없었어요.
A섬 에서 B섬까지 가려면 최소 몇개의 섬을 거쳐야 할까요.?
섬안의 숫자는 그 섬과 연결된 다리의 개수 입니다.
' 인접한 섬' 이란 상하 좌우 대각선 위치에 있는 섬입니다.
다리를 겹쳐서 짓는 것 ( 예: x모양)은 불가능 합니다.
* A.B섬도 포함한 숫자
( A 섬 3 ) ( 1 ) ( 1 ) ( 3 )
( 1 ) ( 2 ) ( 3 ) ( 2 )
( 2 ) ( 2 ) ( 1 ) ( 1 B섬 )