C - Cat Snuke and a Voyage - Harryのブログ

皆さん、あけましておめでとうございます！！

ハリーです。今回は、前回やった BFS（幅優先探索）に関連する問題を解いていきたいと思います。前回の問題とは形式が違った問題ですが、頑張っていきましょう！

C - Cat Snuke and a Voyage
- 問題の概要
- 制約
- 入力例1
- 出力例1
- 入力例2
- 出力例2
- 入力例3
- 出力例3
- 入力例4
- 出力例4
実装方法
ACコード
最後に

C - Cat Snuke and a Voyage

　この問題をやろうと思ったきっかけは、一緒に競プロをやっている友人から BFS を教えてもらった時に、おすすめされたからです。この形式の問題は過去にも何度か出題されているので、しっかりとやっていきたいと思います。

問題の概要

　N個の島からなる諸島があり、これらの諸島の間では船の定期便がM種類運行されています。定期便はそれぞれ $2$ つの島の間を行き来しており、$i$ 種類目の定期便を使うと、島 $ai$ と島 $bi$ の間を行き来する事ができます。

すぬけくんは今島 $1$ にいて、島 $N$$$$ に行きたいと思っています。しかし、島 $1$ から島 $N$ への定期便は存在しないので、定期便を $2$ つ使うことで、島 $N$ に行けるか調べます。

制約

$3 \leq N \leq 200,000$
$1 \leq M \leq \leq 200,000$
$1 \leq ai < bi \leq N$
$(ai,bi) \neq (1,N)$
$i \neq j $ ならば $(ai,bi) \neq (aj,bj)$

入力例1

3 2
1 2
2 3

出力例1

POSSIBLE

入力例2

出力例2

IMPOSSIBLE

入力例3

100000 1
1 99999

出力例3

IMPOSSIBLE

入力例4

出力例4

POSSIBLE

実装方法

まず初めに、collections ライブラリのimport を行います。

 from collections import deque

次に、入力を受け取ります。

まず、NとMの値の入力を受け取ります。さらに、島くを行き来することができるかの判定を行うための、INF の設定と行き来できる島を保存するための配列を作ります。

 n, m = map(int, input().split())
 INF = 10**18
 graph = [ for _ in range(n)]

次に、行き来できる島を受け取り 0-index に値を合わせ配列 graph に値を入れていきます。

 for i in range(m):
   a, b = map(int, input().split())
   a -= 1
   b -= 1
   graph[a].append(b)
   graph[b].append(a)

入力例1の場合だと、graph の要素は下記のような感じになっています。

2
2
3
 [[1], [0, 2], [1]] # graphの中身

距離を保存するための配列を用意します。初期値として、各要素に INF を入れます。

そして、deque オブジェクトを生成します。生成したら初期値の 0 を入れます。

 dist = [INF] * n
 q = deque()
 q.append(0)
 dist[0] = 0

ここの while 文は前回やった幅優先探索の while 文とほとんど一緒で、条件分岐がひとつ減っただけです。INF が入っている場所は行き来することができない場所なので、無視するということになります。

 while q:
   v = q.popleft()
   for i in graph[v]:
       if dist[i] != INF:
           continue
       dist[i] = dist[v] + 1
       q.append(i)

最後に、たどり着けるかどうかの判定を行います。

今回の問題では島 N に定期便を 2 つだけ使うことで、たどり着けるかどうかなので、dist の N-1 番目の要素が 2 以下であればたどり着けるということになります。

 if dist[n-1] <= 2:
     print('POSSIBLE')
 else:
   print('IMPOSSIBLE')

ACコード

 from collections import deque

 n, m = map(int, input().split())
 INF = 10**18
 graph = [ for _ in range(n)]
 for i in range(m):
     a, b = map(int, input().split())
     a -= 1
     b -= 1
     graph[a].append(b)
     graph[b].append(a)

 dist = [INF]*n
 q = deque()
 q.append(0)
 dist[0] = 0
 while q:
     v = q.popleft()
     for i in graph[v]:
       if dist[i] != INF:
             continue
       dist[i] = dist[v] + 1
       q.append(i)

 if dist[n-1] <= 2:
     print('POSSIBLE')
 else:
     print('IMPOSSIBLE')

最後に

　もう2021年がおわり、2022年になりましたね。皆さんが今年の目標や抱負などはあるでしょうか？私は今年、就職活動があるのでいろいろと大変な1年になりそうです...。今年は競プロも就活も両立して頑張りたいと思います。あと、卒業研究もですね...。ではでは、皆さんの1年が良い1年になりますように！それでは皆さん、また来週！