[BOJ] 백준 2667 파이썬 - 단지번호 붙이기

2667번: 단지번호붙이기

 전형적인 BFS의 문제로서 인접해 있는 집들을 하나의 단지로 묶어준 후 

각 단지 내에 있는 집의 수를 오름차순으로 정렬해 주는 문제.

 

<BFS 선언 코드>

def bfs(x, y):
    queue.append([x, y])  # 처음에는 원소가 없으므로 추가 시켜줌
    graph[x][y] = 0  # 중복 방문을 피하기 위해 방문을 했다면 0으로 변환
    count = 1       # 묶여 있는 단지를 세어주기 위한 변수 선언
    while queue:    # queue가 비어있지 않다면
        a, b = queue.pop(0)  # FIFO를 위해 제일 앞자리를 pop 해줌
        for i in range(4):
            q = a + dx[i]
            w = b + dy[i]   # x와 y의 변수의 변화량을 for문으로 적용시켜줌
            # q와 w가 제한조건을 만족하고 방문된적이 없다면
            if 0 <= q < n and 0 <= w < n and graph[q][w] == 1:
                graph[q][w] = 0     # 방문했다는 표시로 해당 그래프의 좌표는 0으로 바꿔주고
                queue.append([q, w])    # queue에 해당 좌표를 추가
                count += 1      # 개수를 세어줌
    return count    # count 리턴

 

<graph 선언 코드>

graph = []
for i in range(n):
    graph.append(list(map(int, input())))   # 입력을 띄어쓰기 없이 한줄씩 받으므로 split없이 작성

 

<count를 정렬해주기 위한 코드>

cnt = []    # 리턴된 count를 저장하기 위한 저장소

for j in range(n):
    for i in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(i, j))   # bfs문 돌림

 

<정답 출력 코드>

cnt.sort()      # 오름차순으로 정렬하라고 했으므로 오름차순으로 정렬해줌
print(len(cnt))  # cnt의 개수를 출력해주고
print(*cnt, sep="\n")   # 각 줄에 cnt의 값을 하나씩 출력해야 하므로 분해 후 출력

 

왠진 모르겠지만 deque를 선언한 후 popleft를 해주는 것보다

pop(0)를 해주는 것이 20% 가량 시간이 줄어들었다.

(96ms -> 72ms)

 

<전체 정답 코드>

n = int(input())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]      # x와 y를 좌표로 보고 각각의 변화량을 선언

graph = []
for i in range(n):
    graph.append(list(map(int, input())))   # 입력을 띄어쓰기 없이 한줄씩 받으므로 split없이 작성

queue = []      # bfs 돌리기 위한 변수 저장소


def bfs(x, y):
    queue.append([x, y])  # 처음에는 원소가 없으므로 추가 시켜줌
    graph[x][y] = 0  # 중복 방문을 피하기 위해 방문을 했다면 0으로 변환
    count = 1       # 묶여 있는 단지를 세어주기 위한 변수 선언
    while queue:    # queue가 비어있지 않다면
        a, b = queue.pop(0)  # FIFO를 위해 제일 앞자리를 pop 해줌
        for i in range(4):
            q = a + dx[i]
            w = b + dy[i]   # x와 y의 변수의 변화량을 for문으로 적용시켜줌
            # q와 w가 제한조건을 만족하고 방문된적이 없다면
            if 0 <= q < n and 0 <= w < n and graph[q][w] == 1:
                graph[q][w] = 0     # 방문했다는 표시로 해당 그래프의 좌표는 0으로 바꿔주고
                queue.append([q, w])    # queue에 해당 좌표를 추가
                count += 1      # 개수를 세어줌
    return count    # count 리턴


cnt = []    # 리턴된 count를 저장하기 위한 저장소

for j in range(n):
    for i in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(i, j))   # bfs문 돌림

cnt.sort()      # 오름차순으로 정렬하라고 했으므로 오름차순으로 정렬해줌
print(len(cnt))  # cnt의 개수를 출력해주고
print(*cnt, sep="\n")   # 각 줄에 cnt의 값을 하나씩 출력해야 하므로 분해 후 출력