2667-番号のみ

20575 ワード
baekjoon plzrun Graph テキストリンク
📚 2667-番号のみ
番号のみ
 
に答える
  • グラフの問題.
  • ツリー検索アルゴリズムです.
    • でも、dfs/bfsどっちが早いですか?
    ポストトラッキング-ツリーウィキ根拠
    🔔 DFSとBFSはいつ使いますか.
    (1)DFSが必要な場合
  • 全ての場合に数量を考慮する場合に使用するDFS
  • ・BFS路はもちろん実現できるがBFS路実現のキューの大きさが増える.スピードも同じだ.
  • そのため、状況の調査は一般DFS比較的便利です.大多数の質問はDFSでも先に答えが出ます.
    • (2)BFSを使用する必要がある場合
  • 木の深さが無限大のとき.
  • 迷路探索中にループが発生した場合DFSそれを逃れることはできない.(DFS使用時にスタックオーバーフローが発生する可能性がある)
  • 木の深さが無限大だったり、迷路探しで回路ができた場合BFS便利です.
  • 最短距離解法問題使用BFS
    •  
    この問題は?すべての場合の数を考慮して、総数を出力する必要があります.使い勝手dfs 
    ソース
    dfs
    import sys

sys.setrecursionlimit(111111)

x_coordinate = [-1 , 0 , 1, 0]
y_coordinate = [0, 1, 0, -1]



def dfs(x, y):
    global result
    result += 1
    visited[x][y] = True

    for i in range(4):
        next_x = x_coordinate[i] + x
        next_y = y_coordinate[i] + y

        if 1<= next_x <= n and 1 <= next_y <=n:
            if visited[next_x][next_y] or graph[next_x][next_y] == 0:
                continue

            dfs(next_x, next_y)


n = int(sys.stdin.readline())

graph = [0]
visited = [[False] * (n+1) for _ in range(n+1)]

total_list = []

for idx in range(n):
    in_graph = list(sys.stdin.readline().strip())
    graph.append([0] + list(map(int, in_graph)))

for i in range(1,n+1):
    for j in range(1, n+1):
        if not visited[i][j] and graph[i][j] == 1:
            result = 0
            dfs(i, j)
            total_list.append(result)

total_list.sort()
print(len(total_list))
print('\n'.join(map(str, total_list)))
     
    採点結果

     
    bfs
    import sys
from collections import deque


x_coordinate = [-1 , 0 , 1, 0]
y_coordinate = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque()
    # print("현재 좌표 : ", x, y)
    queue.append((x, y))
    visited[x][y] = True
    result = 1
    while queue:
        x_out, y_out = queue.popleft()

        for i in range(4):
            next_x = x_out + x_coordinate[i]
            next_y = y_out + y_coordinate[i]

            if next_x < 1 or next_x > n or next_y < 1 or next_y > n:
                continue
            if visited[next_x][next_y]:
                continue
            if graph[next_x][next_y] == 0:
                continue
            visited[next_x][next_y] = True
            result += 1
            queue.append((next_x, next_y))
    return result

n = int(sys.stdin.readline())

graph = [0]
visited = [[False] * (n+1) for _ in range(n+1)]

total_list = []

for idx in range(n):
    in_graph = list(sys.stdin.readline().strip())
    graph.append([0] + list(map(int, in_graph)))

# print(graph)

for i in range(1,n+1):
    for j in range(1, n+1):
        if not visited[i][j] and graph[i][j] == 1:
            result = bfs(i, j)
            total_list.append(result)

total_list.sort()

print(len(total_list))
print('\n'.join(map(str, total_list)))
     
    採点結果
    React Nativeはゼロ単列4ダークモードとi 18 n国際化から
    データベース・リソース・ファイルの処理クラス