Flying Cat Penguin

ゆるゆる仕事、ソフトウェアテスティング関連のことについて綴ります。

AtCoder 修行日記#88

88日目
ABCのC問題に取り組み中。
茶色レベルのD問題も余裕があれば取り組み中。

勉強用のコンテンツはここから。
https://kenkoooo.com/atcoder/#/table/

進捗と一言感想

[C問題] 1問(残り125問)

ABC054: One-stroke Path

数え上げで行けるパターンらしいのですが、解法がdfs(幅優先探索)の問題だったので、他の方の回答を参考にしてAC。
ただ、まだ理解が浅い…他の問題や関連の記事を見てよく復習したいと思います。

def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

n, m = map(int, input().split())

checked = [0] * 8
path = [ [] for _ in range(8)]
for i in range(m):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
  #print(path)
  
print(dfs(0,n,checked,path))
目標
  • まず、今年中に茶色コーダー
学習方針

以上。