[알고리즘] 2667 python BFS

2667: 단지번호붙이기

solved.ac에서 silver 1에 있는 그래프 탐색 문제다.
이것저것 보다 보니까 solved.ac의 문제 레벨이 어떤 기준으로 나뉜 건지 조금 의심이 들기도 하고..
문제를 보고 DFS나 BFS 모두 가능하겠다 생각했는데 개인적으로 BFS에 익숙해지고 싶어서 deque를 사용해서 해결해 보았다.

---

from collections import deque

n = int(input())
g = [[0] * n for _ in range(n)]
visit = [[0] * n for _ in range(n)]
dan = []
que = deque()

for i in range(n):
    g[i] = list(map(int, list(input())))

for i in range(n):
    for j in range(n):
        if g[i][j] == 1 and visit[i][j] == 0:
            que = deque()
            que.append((i, j))
            visit[i][j] = 1
            houses = 0
            while que:
                a, b = que.popleft()
                houses += 1
                if a < n-1: 
                    if g[a+1][b] == 1 and visit[a+1][b] == 0:
                        que.append((a+1, b))
                        visit[a+1][b] = 1
                if b < n-1:
                    if g[a][b+1] == 1 and visit[a][b+1] == 0:
                        que.append((a, b+1))
                        visit[a][b+1] = 1
                if a > 0: 
                    if g[a-1][b] == 1 and visit[a-1][b] == 0:
                        que.append((a-1, b))
                        visit[a-1][b] = 1
                if b > 0: 
                    if g[a][b-1] == 1 and visit[a][b-1] == 0:
                        que.append((a, b-1))
                        visit[a][b-1] = 1
            dan.append(houses)

print(len(dan))
dan.sort()
for i in dan:
    print(i)

저번에 경험한 대로 백준은 numpy를 사용할 수 없기 때문에 list 로 모두 선언해주었다.

위치에 집이 있고, 탐색된 적이 없다면 que에 해당 좌표를 push하고 단지를 만들기 시작한다.
참고로, 처음에

que.append([i, j]) 

의 형태로 좌표를 저장했다가 unpack하는 과정에서 cannot unpack non-iterable int object 같은 오류를 보게 되어서 좌표는 튜플의 형태로 큐에 넣어주었다.

que.append((i, j)) 

단지를 만들기 시작했으면 큐가 빌 때까지 동서남북 네 방향에 집이 있는지 확인하는 작업을 한다.
가장자리에서 탐색하는 경우에 인덱싱 에러가 나올 수 있기 때문에 조건을 걸어주었다.
인접한 집들을 모두 단지에 포함시키면 단지의 가구수를 저장하고 다음 위치에서 탐색을 시작한다.

---

아무래도 아직은 문제 해결에 급급한 것 같다. 깔끔하지도 않고.
코드도 보기에 이뻐야 함 ㅇㅇ