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

2667번 : 단지번호붙이기

 

 

내가 푼 dfs풀이)

import sys
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().rstrip())) for _ in range(n) ]
visit = [ [False]*(n+1) for _ in range(n+1) ] #1
dx = [ 0, 0, -1, 1 ] #2
dy = [ -1, 1, 0, 0 ]
cnt_arr = [] #3
def dfs(x, y): #4
    global cnt
    visit[x][y] = True #5
    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 visit[nx][ny] == False: #6
                visit[nx][ny] = True
                cnt += 1
                dfs(nx, ny)
res = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and visit[i][j] == False: #7
            cnt = 1 #8
            dfs(i, j)
            cnt_arr.append(cnt)
            res += 1
print(res)
for i in sorted(cnt_arr):
    print(i)

 

#1 : 방문처리를 받을 리스트 생성

#2 : 방향벡터

#3 : cnt를 입력받을 리스트

#5 : 첫 호출시 호출위치 방문처리

#6 : 조건에 부합하면 cnt +1, 방문처리, 재귀호출

#7 : 호출 조건

#8 : 첫 아파트 개수에서 호출을 시작하니 0이 아닌 1에서 시작

 

 

 

2) bfs풀이

from collections import deque
n = int(input())
graph = [ list(map(int, input())) for _ in range(n) ]
dx = [ -1, 1, 0, 0 ]
dy = [ 0, 0, -1, 1 ]
answer = []
cnt = 0 #1
res = 0 #2

def bfs(x, y):
    global cnt
    graph[x][y] = 2 #3
    q = deque()
    q.append((x,y)) #4
    
    while q:
        x, y = q.popleft()
        cnt += 1 #5
        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:
                    graph[nx][ny] = 2
                    q.append((nx, ny))
    return cnt #6

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1: #7
            answer.append(bfs(i, j))
            res += 1
            cnt = 0 

answer.sort()
print(res)
for i in answer:
    print(i)

 

#1 : 단지내 세대수를 세어주는 변수

#2 : 단지의 총 갯수

#3 : 처음 방문한 위치(graph[i][j] == 1일때) 방문처리

#4 : 큐에 처음 위치 추가

#5 : 세대 수 추가

#6 : 반복문 끝나면 세대 수 리턴

#7 : 브루트 포스로 반복문 돌면서 단지 찾으면 bfs실행후 cnt(세대 수) answer리스트에 추가하고 총 단지수 +1, 세대 수 초기화

 

이번 문제도 같은 문제를 dfs와 bfs로 풀어볼 수 있는 문제였다. 그래프이론의 기초 잡기에 좋은 문제라고 생각한다.

 

아래는 dfs, 위는 bfs