1012号有機白菜

質問元:https://www.acmicpc.net/problem/1012
迷宮探索などの探索問題.迷宮探索とは違ってDFSとBFSのどちらが有効かは考えられない.

思考過程.

白菜!の数は限られているので、新しい地図を作ったり、白菜を貯蔵したりするよりも、白菜リストの内部でindexを使って調べるほうが効率的かどうか、最初はこのように近いです.

ハクサイの中から1つ抽出し、残りのハクサイリストから選ばれたハクサイの周りにハクサイがあれば、deque探索を利用したハクサイ(deque)に加え、ハクサイリストから見つかったハクサイを取り除く.
[白菜の周りにいるかどうかを判断する方法:方向を利用せず、座標で近づく.(x',y'の和)-(x,yの和)の節五箱は1で、xまたはyのうち1つは同じである.]

重複文を利用すると時間の複雑さが増すと思いますが…

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip("\n"))

# 필드 없이 짤라고 했는데, 그러면 시간복잡도가 너무 커질듯
# 이게 포함되는지 모르니까 K의 요소 하나하나 참조를 해봐야한다.
# 일단 필드 없이 짜보고 필드 있는 걸로도 짜보고 비교하자.

for _ in range(T) :
    M, N, K = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    cabbage = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for k in range(K)]
    warm=0
    while cabbage :
        state = deque([cabbage.pop()])
        while state :
            now = state.popleft()
            for n in cabbage :
                if abs(n[0]+n[1]-now[0]-now[1])==1 and (n[0]==now[0] or n[1]==now[1]) :
                    state.append(n)
                    del cabbage[cabbage.index(n)]
                    #이럴 때 연결리스트를 사용하면 효율적
        warm+=1
    print(warm)

また、for文の内部でfor文変数に触れるエラーを犯さないでください.要素が削除されると、for文は無視されます.

index関数の時間複雑度はO(1)で、それをよく利用しましょう

DFS、BFSで解決.
その結果,DFSとBFSの時間差は大きくなかった.

import sys

T = int(sys.stdin.readline().rstrip("\n"))
dic=[[-1,0],[0,1],[1,0],[0,-1]]

def dfs(state) :
    next_s=[state]
    f[state[0]][state[1]]=0
    while next_s :
        s=next_s.pop() #여기만 pop(0)으로 바꿔주면 bfs
        for n in range(4) :
            ny,nx = s[0]+dic[n][0],s[1]+dic[n][1]
            if ny>=0 and ny<=(N-1) and nx>=0 and nx<=(M-1) and f[ny][nx] == 1 :
                f[ny][nx]=0
                del cabbage[cabbage.index([ny,nx])]
                next_s.append([ny,nx])

for _ in range(T) :
    N, M, K = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    f = [[0 for m in range(M)] for n in range(N)]
    cabbage=[]
    warm=0
    for k in range(K) :
        y,x = list(map(int,sys.stdin.readline().rstrip("\n").split()))
        cabbage.append([y,x])
        f[y][x]=1
    while cabbage :
        dfs(cabbage.pop())
        warm+=1
    print(warm)

DFSではなくSTACKで解決!
他の人がもっと効率的に解いているので,参考にしてみましょう.
mapの各要素でナビゲートするだけです...これが一番速い...?

import sys
sys.setrecursionlimit(10000)

T = int(sys.stdin.readline().rstrip("\n"))
dic=[[-1,0],[0,1],[1,0],[0,-1]]

def dfs(s) :
    for n in range(4) :
        ny,nx = s[0]+dic[n][0],s[1]+dic[n][1]
        if ny>=0 and ny<=(N-1) and nx>=0 and nx<=(M-1) and f[ny][nx] == 1 :
            f[ny][nx]=0
            dfs([ny,nx])

for _ in range(T) :
    N, M, K = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    f = [[0 for m in range(M)] for n in range(N)]
    warm=0
    for k in range(K) :
        y,x = list(map(int,sys.stdin.readline().rstrip("\n").split()))
        f[y][x]=1
    for i in range(N) :
        for j in range(M) :
            if f[i][j]==1 :
                f[i][j]=0
                dfs([i,j])
                warm+=1
    print(warm)

->中間208ミリ秒を無視
実はこれが一番簡単な方法で、キャベツを利用して効率的に作ろうと思っていたのに、もっと大きくなりました.これらのコードを比較し,演算回数を理解し,どのような方法で時間の複雑さを増すかを考える能力を育成すべきである.
1.whileドアが重なる.演算量が多い.
2.del関数のため、もっと時間がかかったようです.del関数の時間複雑度はO(n)である