[Baekjoon] 2667번: 단지번호붙이기 (DFS/BFS Silver1) - Python

1. 문제

---

단지번호붙이기

2. 풀이

---

코드

from collections import deque

def bfs(start_x, start_y):
    count = 0
    queue = deque([(start_x, start_y)])
    visited[start_x][start_y] = 1

    while queue:
        current_x, current_y = queue.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = current_x + dx, current_y + dy
            if 0 < next_x <= n and 0 < next_y <= n and arr[next_x][next_y] == '1' and visited[next_x][next_y] == 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = 1
                count += 1
    return count

def solution():
    global n
    global arr
    n = int(input())
    arr = [list(input()) for _ in range(n)]
    visited = [[0] * n for _ in range(n)]
    ans = []

    for i in range(n):
        for j in range(n):
            if arr[i][j] == '1' and visited[i][j] == 0:
                ans.append(bfs(i, j))
    ans.sort()
    print(len(ans))
    print(*ans, sep="\n")

solution()

입력 및 출력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

>> 3
   7
   8
   9

3. 로직

---

bfs 함수는 시작 좌표 start_x와 start_y를 입력으로 받는다.

1. count 변수를 0으로 초기화하고, 데크(deque)인 queue에 시작 좌표를 넣는다.
   시작 좌표를 방문한 것으로 표시하기 위해 visited[start_x][start_y]를 1로 설정한다.

2. 큐가 비어있지 않은 동안 다음을 반복한다.

• 큐에서 현재 좌표 (current_x, current_y)를 가져온다. (queue.popleft() 메서드를 사용)
• 상하좌우로 이동할 때의 변위를 나타내는 dx, dy 값을 순회한다. ([-1, 0], [1, 0], [0, -1], [0, 1])
• 현재 좌표에서 dx, dy를 더한 값이 맵 내에 있고, 해당 좌표가 1이며 방문하지 않은 경우,
  • 다음 좌표인 (next_x, next_y)를 큐에 추가한다
  • 다음 좌표를 방문한 것으로 표시한다. visited[next_x][next_y]를 1로 설정한다.
  • count 변수를 1 증가시킨다.

3. count 값을 반환한다.

solution 함수

1. n을 입력받고, 크기가 n인 2차원 리스트인 arr을 입력받는다. 방문 여부를 저장하는 2차원 리스트인 visited를 생성합니다. 결과를 저장할 리스트인 ans를 생성합니다.

2. arr을 순회하면서 아직 방문하지 않은 1인 지점을 찾는다.

3. bfs 함수를 호출하여 해당 지점부터 단지 내에 있는 집의 수를 구해서 ans 리스트에 추가한다.

4. ans 리스트의 길이를 구해서 단지수를 출력하고, 오름차순으로 정렬하여 각 단지에 속하는 집의 수를 출력한다.