[백준/Python] 2667번(그래프, DFS, BFS)_단지 번호 붙이기

📌문제 유형

그래프 이론, 그래프 탐색, BFS, DFS (실버1)

 

📌문제

2667번: 단지번호붙이기

 

📌나의 문제풀이

- DFS로 풀이 

n = int(input())
maps = []

for _ in range(n):
    maps.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if maps[nx][ny] == 1:
                maps[nx][ny] = 0
                cnt += 1
                dfs(nx,ny)
    return cnt 

li = []
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1:
            cnt = 1
            maps[i][j] = 0
            cnt = dfs(i,j)
            li.append(cnt)

print(len(li))
li.sort()

for num in li:
    print(num)

 

📌 다른사람의 문제풀이

- BFS 풀이

[백준] 2667 단지번호붙이기 (Python 파이썬)

from collections import deque

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


def bfs(graph, a, b):
    n = len(graph)
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    count = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                count += 1
    return count


n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(graph, i, j))

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

 

📌 리뷰 

- '오름차순' 조건 확인하고 코드 작성하기