[백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1)

문제

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

2667번: 단지번호붙이기

 

 

🐍파이썬

DFS

import sys
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline())
house = []
danzi = []
for _ in range(n):
    house.append(list(map(int, sys.stdin.readline().rstrip())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    global cnt
    if x >= n or y >= n or x < 0 or y < 0:	#배열의 범위를 벗어난 경우 재귀를 빠져나온다
        return
    if house[x][y] == 1:	#집 존재하는 경우
        cnt += 1	#집 갯수 카운팅
        house[x][y] = 0	#방문처리
        for i in range(4):	#상하좌우에 대해 재귀 실행
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)

answer = 0
cnt = 0
for i in range(n):
    for j in range(n):
        if house[i][j] == 1:	#집이 존재하면 재귀 실행
            dfs(i, j)
            danzi.append(cnt)	#cnt값을 리스트에 저장
            answer += 1	#단지의 수
            cnt = 0	#cnt값을 초기화
print(answer)
danzi.sort()	#각 단지의 집 갯수 오름차순 정렬
for i in danzi:
    print(i)

 

 

BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
house = []
danzi = []
for _ in range(n):
    house.append(list(map(int, sys.stdin.readline().rstrip())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    global cnt
    queue = deque()
    queue.append((x, y))
    house[x][y] = 0
    while queue:
        x, y = queue.popleft()
        cnt += 1	#집 갯수 카운팅
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n or ny >= n or nx < 0 or ny < 0:	#배열의 범위를 벗어난 경우 건너뛰기
                continue
            if house[nx][ny] == 0:	#집이 아닌 경우 건너뛰기
                continue
            if house[nx][ny] == 1:	#집인 경우
                house[nx][ny] = 0	#방문처리
                queue.append((nx, ny))	#다음 방문을 위해 현재 좌표 저장

answer = 0
cnt = 0
for i in range(n):
    for j in range(n):
        if house[i][j] == 1:	#집인 경우
            bfs(i, j)	#BFS실행
            danzi.append(cnt)	#카운팅한 집의 갯수를 리스트에 저장
            answer += 1
            cnt = 0	#집 갯수 초기화
print(answer)
danzi.sort()	#오름차순 정렬
for i in danzi:
    print(i)