Pythonアルゴリズム066|番号のみ(DFS、*BFS*)****
66.番号のみ（DFS、BFS）
図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それは家をつなぐ集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.
図2は、図1を個別に番号付けしたものである.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.
■説明の入力
1行目は地図の大きさN(正方形,横方向,縦方向の大きさが同じ,5≦N≦25)を入力した.
はい、その後、N行にN個の資料(0または1)を入力します.
■出力説明
最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べます.
行ごとに1つ印刷
■入力例1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
■出力例1
3
7
8
9
『私の答え』
まず上下左右をぐるっと回って確認してみます.
周りに行く場所がなければ、別の端に移動したいです.
1つのエッジ(0,n)−(n,0)−(n,n)−(n,n)のみ
(1)-プールを試して実装しますが、いくつかの障害があります.
=>dfs終了後、冗長for文を返す方法
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
global cnt
if #이 부분을 어떻게 설정해줘야 dfs를 끝낼 수 있는지 모르겠음
res.append(cnt) #=>이 부분을 굳이 if 에 안넣어도 되고 밑에 dfs호출하고 난 뒤에 넣어주면 된다, dfs다 겪은 후에
else :
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
a[xx][yy]=0
cnt+=1
dfs(xx,yy)
if __name__=='__main__' :
cnt=0 #=> cnt를 여기다가 두면 초기화가 되지 않고 계속해서 누적이 되고 만다
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
a[i][j]=0
dfs(i,j)
res.sort()
print(len(res))
for i in res:
print(i)
=>>ただし、ここにもエラーがある場合は、dfsを呼び出す前にcntが呼び出されます.
dfsでは、最初の値はcntに追加されませんので、最初はcnt=1に初期化する必要があります.
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
global cnt
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
a[xx][yy]=0
cnt+=1
dfs(xx,yy)
if __name__=='__main__' :
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
cnt=0
a[i][j]=0
dfs(i,j)
res.append(cnt)
res.sort()
print(len(res))
for i in res:
print(i)
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y):
global cnt
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
a[xx][yy]=0
cnt+=1
dfs(xx,yy)
if __name__=='__main__' :
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
cnt=1 #=> cnt를 1로 설정했어야 한다. 선생님은 dfs 호출한 이후에 1을 꼬박꼬박 더해줬기에 여기를 0으로 했지만 나는 처음거는 안세주기 때문에 여기서 하나 세주어야 한다
a[i][j]=0
dfs(i,j)
res.append(cnt)
res.sort()
print(len(res))
for i in res:
print(i)<解答>
(1)まず2階建てforドアで,1行ごとにチェックし,発見1から
dfsを呼び出し,上下左右探索を行う.
そしてこの部分を0に変えます.
cnt+=1(数しか数えられないため)
(2)全てが詰まっている場合、1つのdfsを終了する-リストに数桁を追加する
(3)一つのdfsが終わったら、先ほどのダブルforゲート回転部分に戻る
(4)ナビゲーション中に1が見つかった場合、ナビゲーションして0に置き換え、カウントする
[1] DFS
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def dfs(x, y):
global cnt
cnt+=1 #하나가 넘어오면 카운트 시작 일단
a[x][y]=0
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
dfs(xx,yy)
if __name__=="__main__":
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
cnt=0 #여기서 초기화를 해줬어야 한다! 단지마다 세는 것이니깐
dfs(i,j)
res.append(cnt) #res에 cnt더해주는 것 여기서 하기
res.sort()
print(len(res))
for i in res:
print(i)
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
n=int(input())
board=[list(map(int, input())) for _ in range(n)]
cnt=0
res=[]
Q=deque()
for i in range(n):
for j in range(n):
if board[i][j]==1:
board[i][j]=0
Q.append((i, j))
cnt=1
while Q:
tmp=Q.popleft()
for k in range(4):
x=tmp[0]+dx[k]
y=tmp[1]+dy[k]
if x<0 or x>=n or y<0 or y>=n or board[x][y]==0:
continue
board[x][y]=0
Q.append((x, y))
cnt+=1
res.append(cnt)
print(len(res))
res.sort()
for x in res:
print(x)
『反省点』
『学んだこと』
その時になってやっとdfsを呼んで、上下左右に回って1人の子供を探していたら
1人の子供たちを0に変えて、全部見つけたら、再び門の前に戻り、
覚えておくと他は子供が会うだけでも0なので、彼らの方法は含まれないでください.
<第2話毒ガス放出>
def dfs(x,y) :
global cnt
for i in range(4) :
cnt+=1 #이걸 여기다가 두어서 오류, 이 for문 돌리기전에 넣어줘야지
a[x][y]=0 #이것두
xx=dx[i]+x
yy=dy[i]+y
if 0<=xx<n and 0<=yy<n and a[xx][yy]==1:
dfs(xx,yy)
if __name__=='__main__' :
res=[]
cnt=0
dx=[-1,0,1,0]
dy=[0,-1,0,1]
n=int(input())
a=[list(map(int,input())) for _ in range(n)]
for i in range(n) :
for j in range(n):
if a[i][j]==1:
cnt=0
dfs(i,j)
res.append(cnt)
print(res)
def dfs(x,y) :
global cnt
cnt+=1
a[x][y]=0
for i in range(4) :
xx=dx[i]+x
yy=dy[i]+y
if 0<=xx<n and 0<=yy<n and a[xx][yy]==1:
dfs(xx,yy)
if __name__=='__main__' :
res=[]
cnt=0
dx=[-1,0,1,0]
dy=[0,-1,0,1]
n=int(input())
a=[list(map(int,input())) for _ in range(n)]
for i in range(n) :
for j in range(n):
if a[i][j]==1:
cnt=0
dfs(i,j)
res.append(cnt)
print(len(res))
for i in res:
print(i)Reference
この問題について(Pythonアルゴリズム066|番号のみ(DFS、*BFS*)****), 我々は、より多くの情報をここで見つけました https://velog.io/@myway00/066-단지-번호-붙이기DFS-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol