番号のみ(DFS、BFS)

インプリメンテーションコード

# 단지 번호 붙이기 (DFS, BFS)
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")

def BFS(blankX, blankY):
    Q = deque()
    Q.append((blankX, blankY))
    isOne = False
    while Q:
        tmp = Q.popleft()
        for j in range(5):
            x = tmp[0]+dx[j] # x좌표
            y = tmp[1]+dy[j] # y좌표
            if 0<=x<n and 0<=y<n:
                if board[x][y] == 1 and ch[x][y] == 0:
                    isOne = True
                    ch[x][y] = 1
                    res[x][y] = L
                    cnt[L-1] += 1
                    Q.append((x,y))
                if board[x][y] == 0 and ch[x][y] == 0:
                    ch[x][y] = 1
                    res[x][y] = 0

    return isOne

if __name__ == "__main__":
    n = int(input())
    board = []
    for _ in range(n):
        board.append(list(map(int, input())))
    res = [[-1 for _ in range(n)] for _ in range(n)]

    # 상하좌우 좌표
    dx = [0, -1, 0, 1, 0]
    dy = [0, 0, 1, 0, -1]

    ch = [[0 for _ in range(n)] for _ in range(n)]

    L = 1
    isdone = False
    cnt = []

    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                res[i][j] = 0
            else:
                if res[i][j] == -1:
                    cnt.append(0)
                    isOne = BFS(i,j)
                    if isOne:
                        L += 1

    print(L-1)
    cnt.sort()
    for x in cnt:
        print(x)

ベストアンサー(DFS)

import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]

def DFS(x, y):
    global cnt
    cnt+=1
    board[x][y]=0 #이렇게 처리하였기 때문에 한번 방문한 곳은 재방문 x
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
            DFS(xx, yy)

if __name__=="__main__":
    n=int(input())
    board=[list(map(int, input())) for _ in range(n)]
    res=[]
    for i in range(n):
        for j in range(n):
            if board[i][j]==1:
                cnt=0
                DFS(i, j)
                res.append(cnt)
    print(len(res))
    res.sort()
    for x in res:
        print(x)

ベストアンサー(BFS)

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)

差異