[백준] 2667번 : 단지번호붙이기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2667번: 단지번호붙이기

 

1. 문제 설명

2. 풀이과정

해당 문제는 넓이 우선 탐색을 활용하여 상, 하, 좌, 우 4방향을 매번 탐색해 각 단지별로 연결된 집을 찾아 개수를 세는 방법으로 해결하였다. 그래프를 생성하고 각 단지의 시작을 찾아 넓이 우선 탐색을 진행하고 탐색한 집은 1에서 0으로 바꾸어 탐색을 진행하였다. 각 단지별로 집의 개수를 각각 세어 저장하고 이를 정렬해 출력해 주었다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 넓이 우선 탐색에서 popleft() 함수를 사용하기 위해 deque 자료구조를 만들어 사용하는데 이를 위해 deque 모듈을 불러온다. from collections import deque
3. 넓이 우선 탐색 함수를 생성한다. def BFS(row, col)
4. 지도의 크기를 입력받는다. N = int(sys.stdin.readline())
5. 각 위치별 집의 정보를 저장할 그래프를 리스트로 생성한다. graph = list()
6. 각 행별로 정보를 입력받고 이를 리스트로 그래프에 저장한다. 이때 각 행별 정보는 enter로 구분되어 있기 때문에 마지막에 enter는 제거하고 저장한다. for i in range(N): graph.append(list(sys.stdin.readline().rstrip()))
7. 상, 하, 좌, 우 4방향으로 집을 탐색하기 위해 각 방향 별 행과 열의 변환 정보를 담은 리스트를 생성한다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
8. 각 단지별 집의 개수를 저장할 리스트를 생성한다. result = list()
9. 0, 0 위치부터 탐색하여 각 단지의 시작 위치를 찾는다. for i in range(N): for j in range(N)
10. 만약 단지의 시작 위치의 집을 찾으면 해당 위치를 시작으로 넓이 우선 탐색을 수행하며 한 단지 내의 집들을 탐색한다. if (graph[i][j] == '1'): BFS(i, j)
11. 모든 단지의 집을 탐색하면 단지의 개수를 출력한다. print(len(result))
12. 단지별 집의 개수를 오름차순으로 정렬하고 result.sort()
13. 이를 한 줄씩 출력한다. for i in result: print(i)

 

BFS 함수 설명

1. 탐색할 위치 정보를 저장할 deque를 생성한다. queue = deque()
2. 매개변수로 입력받은 초기 탐색 집의 위치를 추가한다. queue.append([row, col])
3. 한 번 탐색한 집은 0으로 바꿔 중복을 막아준다. graph[row][col] = '0'
4. 각 단지별 집의 개수를 저장할 변수를 생성하고 1로 초기화한다. count = 1
5. 탐색할 위치 정보 deque이 공백이 될 때까지 반복한다. while (queue)
6. 위치 정보를 앞에서부터 가져와 행과 열로 저장한다. row, col = queue.popleft()
7. 상, 하, 좌, 우 4방향으로 탐색한다. for i in range(len(move))
8. 다음으로 탐색할 위치를 새로 저장한다. nextRow = row + move[i][0]  nextCol = col + move[i][1]
9. 만약 다음으로 탐색할 위치가 지도 안에 위치하고 집이 존재하며, 처음 탐색한다면 if (0 <= nextRow < N and 0 <= nextCol < N and graph[nextRow][nextCol] == '1')
10. 다음 위치 정보를 추가한다. queue.append([nextRow, nextCol])
11. 탐색한 집을 0으로 바꿔준다. graph[nextRow][nextCol] = '0'
12. 집을 탐색했으므로 단지 내 집의 개수를 1 증가시킨다. count += 1
13. 한 단지 내 연결되어 있는 모든 집을 탐색했다면 집의 개수를 결과에 추가한다. result.append(count)

반응형

3. 소스코드

import sys
from collections import deque

def BFS(row, col):
    queue = deque()
    queue.append([row, col])
    graph[row][col] = '0'

    count = 1
    while (queue):
        row, col = queue.popleft()

        for i in range(len(move)):
            nextRow = row + move[i][0]
            nextCol = col + move[i][1]

            if (0 <= nextRow < N and 0 <= nextCol < N and graph[nextRow][nextCol] == '1'):
                queue.append([nextRow, nextCol])
                graph[nextRow][nextCol] = '0'
                count += 1

    result.append(count)

N = int(sys.stdin.readline())

graph = list()
for i in range(N):
    graph.append(list(sys.stdin.readline().rstrip()))

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]

result = list()

for i in range(N):
    for j in range(N):
        if (graph[i][j] == '1'):
            BFS(i, j)

print(len(result))

result.sort()
for i in result:
    print(i)