［アルゴリズム］BOJ 1260 DFSとBFS
8002 ワード
[BOJ]1260 DFSとBFSのショートカット
📍 質問する
DFSを使用してグラフィックをナビゲートし、BFSを使用してグラフィックをナビゲートした結果を出力するプログラムを作成します.ただし、複数のアクセス可能な頂点がある場合は、最初にアクセスできる頂点番号が小さく、アクセスできるポイントがない場合は終了します.頂点番号は1番からN番までです.
📍 入力
1行目は頂点の個数N(1≦N≦1000)、幹線の個数M(1≦M≦10000)、探索を開始する頂点の番号Vを与える.次のM行は、幹線接続の2つの頂点の番号を示します.2つの頂点の間に複数の幹線があります.入力された幹線は双方向です.
📍 しゅつりょく
1行目はDFSを実行した結果を出力し、2行目はBFSを実行した結果を出力する.Vから順にアクセスポイントを出力すればよい.
📍 に答える
ハーモニー
from sys import stdin
from collections import deque
def DFS(v, visited):
print(v, end=" ")
visited[v] = False # 방문한 노드 체크
for i in arr[v]:
if visited[i]: # 방문하지 않은 노드
DFS(i,visited) # DFS 재귀
def BFS(v, visited):
visited[v] = False
D = deque([v])
while D:
tmp = D.popleft() # 제일 앞 노드
print(tmp,end=" ")
for i in arr[tmp]:
if visited[i]: # 방문하지 않은 노드
visited[i] = False
D.append(i) # 방문 리스트에 추가
N, M, V = map(int,stdin.readline().split())
arr = [ [0 for _ in range(N+1)] for _ in range(N+1) ]
for _ in range(M):
x, y = map(int,stdin.readline().split())
arr[x][y] = y
arr[y][x] = x
visited = [False]+[True for _ in range(N)]
DFS(V, visited)
print()
visited = [False]+[True for _ in range(N)]
BFS(V, visited)Reference
この問題について(［アルゴリズム］BOJ 1260 DFSとBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@isayaksh/알고리즘-BOJ-1260-DFS와-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol