[파이썬/Python] 백준 2667번: 단지번호붙이기

숨·2024년 8월 11일

📌 문제 탐색하기

N : 지도의 가로, 세로 크기 ( $5≤N≤25$ )

✅ 입력 조건
1. N 입력
2. N번 반복해 자료 입력
✅ 출력 조건
1. 총 단지 수 출력
2. 오름차순 정렬 후 순서대로 각 단지 내 집의 수 한 줄 씩 출력

N x N 크기의 지도에서 각 단지 내 집의 수를 구해 출력하는 문제이다.

지도에서 0 → 집 ❌ / 1 → 집 ⭕️을 의미한다.

단지 = 상하좌우로 연결된 집들의 모임을 의미하므로 연결된 집들을 모두 찾는 탐색 기법을 활용하면 된다.
→ 집의 위치 찾기
→ 이미 지나간 집은 0으로 변경하여 방문 처리
→ BFS를 이용해 특정 집과 연결된 집이 있는지 탐색
→ 집의 수 카운트
→ 위의 과정을 연결된 집이 없을 때까지 반복
→ 최종 집의 수 저장
하여 원하는 출력을 얻으면 될 것이다.

가능한 시간복잡도

지도 입력 → $O(N^2)$
단지 찾는 BFS → $O(N^2)$
오름차순 정렬 → $O(단지수 * log(단지수))$

최종 시간복잡도
$O(N^2)$
최악의 경우 $O(25^2) = O(625)$ 이 된다.
이는 1초 내에 연산이 가능하다.

알고리즘 선택

집이 있는 위치에서 연결된 집이 몇 채인지 BFS로 탐색하기

📌 코드 설계하기

BFS 함수 구현
N 입력
지도 입력
연결된 집 찾는 BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

# 지도 입력
map_info = [list(map(str, input().split())) for _ in range(N)]

# 방문 안한 집의 위치 찾아 bfs 수행
for i in range(N):
    for j in range(N):
        if map_info[i][j] == 1:  # 에러 발생 위치
            print(bfs(i, j))

입력 받은 지도를 이중 for문으로 돌면서 지도 위치를 인덱스로 접근하려 했는데 j에서 IndexError: list index out of range가 발생했다.
input().split()로 입력 받아 한줄을 분리하지 않고 저장해서 발생한 일이었다. 그 한줄을 int로 받으면 앞부분의 0이 사라지는 문제도 있었다.

# 해결) 지도 입력
map_info = [list(map(int, input().rstrip())) for _ in range(N)]

rstrip()로 개행 문자를 제거하고, 각 숫자를 분리 후 저장하는 방식으로 변경하여 해결했다.

2회차

if 0 <= nx < N and 0 <= ny < N and map_info[nx][ny] == 1:  # 방문 확인 빠짐
    # 집의 수 세기
    count += 1
    # 방문 처리
    visited[nx][ny] = 0 ### 방문 처리 잘못함
    # 탐색 지속
    queue.append((nx, ny))
    
#########  

# 방문 안한 집의 위치 찾아 bfs 수행
for i in range(N):
    for j in range(N):
        if map_info[i][j] == 1:  # 방문 확인 빠짐
            print(bfs(i, j))

이렇게 구현하였는데 아무런 출력이 나오지 았다.
방문 위치 확인 단계를 빠트렸다.
방문 리스트를 따로 정의하지 않고 하는 아이디어와 방문 리스트를 이용하는 아이디어를 섞어서 생각하는 바람에 방문 처리를 1이 아닌 0으로 바꾸는 식으로 작성한 부분이 있어 수정했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 함수 구현
def bfs(x, y):
    queue = deque([(x, y)])
    # 방문 처리
    visited[x][y] = 1
    # 집의 수 초기화
    count = 1
    # 큐 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        for direction in directions:
            nx, ny = x + direction[0], y + direction[1]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and map_info[nx][ny] == 1:
                # 집의 수 세기
                count += 1
                # 방문 처리
                visited[nx][ny] = 1
                # 탐색 지속
                queue.append((nx, ny))
    # 집의 수 리턴
    return count


# N 입력
N = int(input())

# 지도 입력
map_info = [list(map(int, input().rstrip())) for _ in range(N)]

# 방문 리스트 초기화
visited = [[0] * N for _ in range(N)]

# 이동 방향 정의
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 집의 수 저장할 리스트 초기화
houses_num = []

# 방문 안한 집의 위치 찾아 bfs 수행
for i in range(N):
    for j in range(N):
        if map_info[i][j] == 1 and not visited[i][j]:
            houses_num.append(bfs(i, j))

# 오름차순 정렬
houses_num.sort()

# 단지 수 출력
print(len(houses_num))

# 결과 출력
for num in houses_num:
    print(num)