백준 2667: 단지번호붙이기 (Python)

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

리스트 돌면서 해당 데이터가 1이면 상하좌우 살피면서 그래프를 탐색한다.

코드가 매우 너저분한 느낌,,,

 

# dfs

n = int(input())
list = [[] for _ in range(n)]

for i in range(n):
    data = input()
    for j in range(n):
        list[i].append(int(data[j]))

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    if list[x][y] == 1:
        global count
        count += 1
        list[x][y] = 0
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    else:
        return False

cList = []
result = 0

for i in range(n):
    for j in range(n):
        count = 0
        if dfs(i, j):
            cList.append(count)
            result += 1

cList.sort()
print(result)
for i in range(len(cList)):
    print(cList[i])

# bfs

from collections import deque

n = int(input())
list = [[] for _ in range(n)]

for i in range(n):
    data = input()
    for j in range(n):
        list[i].append(int(data[j]))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    global count
    queue = deque()

    if list[x][y] == 1:
        queue.append([x, y])
        list[x][y] = 0

        while queue:
            q1, q2 = queue.popleft()
            count += 1

            for i in range(4):
                mx = q1 + dx[i]
                my = q2 + dy[i]

                if mx < 0 or mx >= n or my < 0 or my >= n:
                    continue

                if list[mx][my] == 1:
                    queue.append([mx, my])
                    list[mx][my] = 0

    return count

result = 0
cList = []
for i in range(n):
    for j in range(n):
        count = 0
        if bfs(i, j) > 0:
            result += 1
            cList.append(count)

cList.sort()
print(result)
for i in range(len(cList)):
    print(cList[i])