백준 2667. 단지번호붙이기

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

2667번: 단지번호붙이기

BFS 이용(48ms)

def bfs(sti,stj):
    q = []  # 큐 생성
    cnt = 1  # 본인 포함이므로 디폴트가 1
    arr[sti][stj] = 0  # 본인은 방문했으니 0으로 바꿔줌
    q.append((sti,stj))  # 큐에 본인좌표 넣기
    while q:  # 큐가 빌 때까지
        i, j = q.pop(0)  # 맨 앞의 큐 꺼내오기
        for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:  # 네방향 탐색하자!
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < n and arr[ni][nj]:  # 유효한 인덱스 범위이고, 1(아직 방문x)이면
                q.append((ni, nj))  # 큐에 해당좌표 넣고
                arr[ni][nj] = 0  # 해당좌표 방문표시 해주기!
                cnt += 1  # 집 수 누적합
    return cnt


n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
result = []
for i in range(n):
    for j in range(n):
        if arr[i][j]:  # arr에서 1이나오면 거기를 시작으로 탐색시작
            result.append(bfs(i,j))  # 그곳의 1을 시작으로 센 집 수를 result에 저장
result.sort()  # 오름차순 출력이므로 정렬해줌
print(len(result))  # 단지수
for i in result:    # 단지내 집 수 한줄에 하나씩 출력
    print(i)

따로 visited를 만들어주지 않고 입력받은 배열로 방문처리를 해주고 count를 해주고 리턴해줌!

---

 재귀 DFS 이용(44ms)

def dfs(sti,stj):
    global cnt
    if sti < 0 or sti >= n or stj < 0 or stj >= n:  # 유효하지 않은 인덱스면
        return  # while문에서 break과 같은 역할
    if arr[sti][stj]:
        cnt += 1
        arr[sti][stj] = 0
        for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            ni, nj = sti + di, stj + dj
            dfs(ni,nj)  # 재귀함수


n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
result = []
cnt = 0
for i in range(n):
    for j in range(n):
        if arr[i][j]:
            dfs(i,j)
            result.append(cnt)
            cnt = 0
result.sort()
print(len(result))
for i in result:
    print(i)