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

백준 문제 풀이 - 그래프 탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000 

>> 3
>> 7
>> 8
>> 9

💬 풀이

🎵 첫번째 풀이 - DFS

import sys


input = sys.stdin.readline
N = int(input())    # 지도의 크기
graph = [list(map(int, input().rstrip())) for _ in range(N)]

visited = [[False] * N for _ in range(N)]    # 방문 처리
count = 0

dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]


def dfs(r, c):
    visited[r][c] = True
    global count
    count += 1

    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]

        if nr < 0 or nc < 0 or nr >= N or nc >= N or visited[nr][nc] or not graph[nr][nc]:
            continue

        dfs(nr, nc)


answers = []
ans = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] and not visited[i][j]:
            dfs(i, j)
            answers.append(count)
            ans += 1
            count = 0

print(ans)
for a in sorted(answers):
    print(a)

🎵 두번째 풀이 - BFS

from collections import deque
import sys


input = sys.stdin.readline
N = int(input())    # 지도의 크기
graph = [list(map(int, input().rstrip())) for _ in range(N)]

visited = [[False] * N for _ in range(N)]    # 방문 처리
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]


def bfs(r, c):

    q = deque()

    q.append((r, c))
    visited[r][c] = True

    count = 1

    while q:
        nowr, nowc = q.popleft()

        for d in range(4):
            nr = nowr + dr[d]
            nc = nowc + dc[d]

            if nr < 0 or nc < 0 or nr >= N or nc >= N or visited[nr][nc] or not graph[nr][nc]:
                continue
            
            count += 1

            q.append((nr, nc))
            visited[nr][nc] = True

    return count


answers = []
ans = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] and not visited[i][j]:
            ans += 1
            answers.append(bfs(i, j))

print(ans)
for a in sorted(answers):
    print(a)

✒️ 생각