백준 2667 단지번호 붙이기 Python 실버1 그래프 BFS

정답 코드 1

# 2667 단지번호 붙이기
from collections import deque
def bfs(y,x):
    global cnt
    num = 0
    if arr[y][x] ==0: return
    if visited[y][x]: return
    Q = deque()
    Q.append((y,x))
    while Q:
        y,x = Q.popleft()
        num += 1
        visited[y][x] = 1
        if arr[y][x] == 1: arr[y][x] += cnt
        for direct in dij: # 4방향
            di = y + direct[0]
            dj = x + direct[1]
            if 0 <= di < n and 0 <= dj < n: # 벽 체크
                if visited[di][dj] == 0: # 안 가본곳이라면
                    if arr[di][dj] ==0:
                        visited[di][dj] = 1
                    else:
                        arr[di][dj] += cnt
                        visited[di][dj] = 1
                        Q.append((di,dj))
    cnt += 1
    path.append(num)

n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
dij = [[0,1],[1,0],[0,-1],[-1,0]] # 오 아 왼 위
visited = [[0] * n for _ in range(n)]
path = []
cnt = 0
# 시작 지점
for i in range(n):
    for j in range(n):
        bfs(i, j)

# for p in arr:
#     print(p)
# print(visited)
# print(cnt)
# print(path)
path.sort()
print(cnt)
for i in path:
    print(i)

정답코드 2 (오답코드 수정한 코드)

# 2667 단지번호 붙이기
from collections import deque
def bfs(y,x):
    global cnt
    Q = deque()
    Q.append((y,x))
    visited[y][x] = 1
    arr[y][x] = cnt
    while Q:
        y,x = Q.popleft()
        visited[y][x] = 1
        for direct in dij: # 4방향
            di = y + direct[0]
            dj = x + direct[1]
            if 0 <= di < n and 0 <= dj < n and arr[di][dj] and visited[di][dj] == 0:  # 벽체크 + 0이면 안간다
                arr[di][dj] = cnt
                visited[di][dj] = 1
                Q.append((di,dj))


n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
dij = [[0,1],[1,0],[0,-1],[-1,0]] # 오 아 왼 위
visited = [[0] * n for _ in range(n)]
cnt = 1


for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            bfs(i,j)
            cnt += 1

path = []
for k in range(1,cnt+1):
    cnt_num = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] == k:
                cnt_num += 1
    if cnt_num != 0:
        path.append(cnt_num)

# for isss in arr:
#     print(isss)
path.sort()
print(len(path))
for i in path:
    print(i)

오답 코드

# 2667 단지번호 붙이기
from collections import deque
def bfs(y,x):
    global cnt
    Q = deque()
    Q.append((y,x))
    visited[y][x] = 1
    while Q:
        y,x = Q.popleft()
        visited[y][x] = 1
        for direct in dij: # 4방향
            di = y + direct[0]
            dj = x + direct[1]
            if 0 <= di < n and 0 <= dj < n and arr[di][dj] and visited[di][dj] == 0:  # 벽체크 + 0이면 안간다
                arr[di][dj] += cnt
                visited[di][dj] = 1
                Q.append((di,dj))

def find_pos():
    flag = 1
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 1:
                r, c = i,j
                return (r,c-1)
    flag = 0
    return flag
n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
dij = [[0,1],[1,0],[0,-1],[-1,0]] # 오 아 왼 위
visited = [[0] * n for _ in range(n)]
cnt = 1

while True:
    if find_pos():
        r, c = find_pos()
        bfs(r, c)
        cnt += 1
    else:
        break

path = []
for k in range(2,cnt+1):
    cnt_num = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] == k:
                cnt_num += 1
    if cnt_num != 0:
        path.append(cnt_num)
path.sort()
print(len(path))
for i in path:
    print(i)