[백준 2167] 단지 번호 붙이기 (python)

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

 

 

 

 

풀이

#단지 번호 붙이기
from collections import deque
from importlib.resources import contents

#새로운 단지를 찾아주는 함수
def findNewStart(board, visited, N):
    for i in range(N):
        for j in range(N):
            if [i,j] not in visited:
                if board[i][j] == "1":
                    return i, j
    return -1,-1

def BFS(board, N):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    village = []
    visited = []
    cnt = 0
    x, y = 0,0 
    queue = deque()
    x , y = findNewStart(board, visited, N)           
    while x !=  -1 and y != -1:
        #print("new vilage start ", x ," ", y)
        queue.append([x,y])
        while queue:
            n = queue.popleft()
            #print("n = ", n )
            if n not in visited:
                visited.append(n)
                cnt += 1
                for i in range(4):
                    tmpx = n[0] + dx[i]
                    tmpy = n[1] + dy[i]
                    if tmpx >= 0 and tmpy >= 0 and tmpx <N and tmpy <N and  [tmpx, tmpy] not in visited:
                        if board[tmpx][tmpy] == "1":
                            queue.appendleft([tmpx, tmpy])
                        else:
                            visited.append([tmpx,tmpy])
        village.append(cnt)
        cnt = 0
        x, y = findNewStart(board, visited, N)
    return village


#입력 
N = int(input())
board = []
test = []
for _ in range(N):
    board.append(list(input()))

ans = BFS(board, N)

print(len(ans))
ans.sort()
for _ in (ans):
    print(_)

 

소감과 배운점

 

코드가 조금 지저분 하게 짜졌는데, 이유를 생각해 보니

이 문제에서는 bfs로 풀 경우 bfs를 여러번 사용하애 한다.

그런데 나는 BFS 함수 안에서 bfs를 여러번 반복했기 때문에 지저분 하게 풀린것 같다. 

다음에는 분리해서 풀어야 겠다. 

 

그리고 저번 미로 문제에서는 if문 네개로 방향을 탐색했는데  

아래의 방법으로 푸는게 훨씬 깔끔하다. 

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

 

처음에는 python이 너무 불편했는데

조금 적응하니 정말 편하다ㅎㅎ 그냥 리스트에 다 때려박으면 알아서 해줌