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

반응형

 

난이도 : 실버 1

알고리즘 유형 : BFS/DFS (너비우선탐색을 이용하여 품 

문제 링크 : https://www.acmicpc.net/problem/2667

 

문제 풀이과정

 

DFS와 BFS를 수업에서 들었지만, 생각보다 머리에 파고들지 않아서 동빈북을 보면서 코드를 쳐보고, 써보고, 그래프를 DFS로 따라가보고, BFS로 따라가보며 마치 목기에 옻칠하듯이 여러번 반복하다가, 이제 좀 코드가 나오겠다 싶을 때 도전한 문제이다.

DFS로 구현해보려다가, 정형화된 인접리스트나 인접행렬을 만들 방도가 떠오르지 않아 BFS로 접근하였다.

구현방식은 단지정보 2차원 배열을 순회하다가 '1' 이 나오면 bfs 함수 호출.

이때 함수를 호출 할때 cnt 변수를 +1 해준다. 이는 단지의 수를 의미한다.

함수에서는 단지정보 배열에서 '1' 을 찾으면 villicnt 변수를 +1 해주며 단지정보 배열에서 발견된 '1' 을 지운다. 또 델타를 사용하여 가로세로로 이동하며 이를 반복한다. 이때 방문한 좌표는 가지 않게 설정하며 함수가 끝나면 villicnt 변수를 반환한다. 이는 함수가 찾아낸 단지내 세대의 총합을 의미한다. 

함수가 끝나면 함수에서 찾은 값을 리스트 villi 에 넣는다. 이는 단지내 세대를 오름차순으로 배열하기 위함이다. 

그리고 단지정보 순회가 끝나면

단지의 수(cnt)를 출력해주고

villi를 순회하며 출력해준다. 

---

 

from collections import deque

def bfs(r, c, graph):
    villicnt = 0
    deq = deque([])
    deq.append((r, c))
    visited = [[False] * N for _ in range(N)]
    visited[r][c] = True
    graph[r][c] = 0
    villicnt += 1
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    while deq:
        r, c = deq.popleft()
        for i in range(4):
            rr = r + dr[i]
            cc = c + dc[i]
            if 0 <= rr < N and 0 <= cc < N:
                if graph[rr][cc] =='1' and not visited[rr][cc]:
                    deq.append((rr, cc))
                    graph[rr][cc] = 0
                    visited[rr][cc] = True
                    villicnt += 1
    return villicnt


N = int(input())
mat = [list(input()) for _ in range(N)]
cnt = 0
villi = []
for r in range(N):
    for c in range(N):
        if mat[r][c] == '1':
            villi.append(bfs(r, c, mat))
            cnt += 1
print(cnt)
villi.sort()
for i in villi:
    print(i)

 

 

---