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

문제

2667번: 단지번호붙이기

풀이

DFS

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

def dfs(graph, x, y, visited):
    global c
    c += 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] == "1" and not visited[nx][ny]:
                visited[nx][ny] = c
                dfs(graph, nx, ny, visited)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(3000000)

n = int(input())

graph = [list(input()) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

cnt = 0
c_li = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == "1" and visited[i][j] == 0:
            # c가 마지막에 돌다가 그대로 나오기 때문에 0부터 시작
            c = 0
            visited[i][j] = 1
            dfs(graph, i, j, visited)
            cnt += 1
            c_li.append(c)

print(cnt)
for _ in sorted(c_li):
    print(_)

해설

입력이 붙어서 입력되기 때문에 문자열로 받아서 list에 넣어서 하나하나 떨어뜨려주었다.
그래서 문자열 "1"을 기준으로 문제풀이 하였다.
여기서 단지의 크기를 나타내는 c를 가정 전에 +=을 해서 마지막에 1이 더 크게 나와서 0부터 시작하게했다.
1부터 시작하고 싶다면 visited[nx][ny] = c 전에 c += 1 넣어주면 될 것같다.

BFS

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

from collections import deque
def bfs(graph, x, y, visited):
    global c
    q = deque([(x, y)])
    visited[x][y] = 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == "1" and not visited[nx][ny]:
                    q.append((nx, ny))
                    c += 1
                    visited[nx][ny] = c


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3000000)

n = int(input())

graph = [list(input()) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

cnt = 0
c_li = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == "1" and visited[i][j] == 0:
            c = 1
            bfs(graph, i, j, visited)
            cnt += 1
            c_li.append(c)

print(cnt)
for _ in sorted(c_li):
    print(_)