전형적인 2차원 그래프 탐색 문제다.
BFS(너비 우선 탐색)로 풀었다. 탐색 위치 0으로 바꿔서 방문을 없앤다.
단지(connected component)의 총 개수와 각 단지에 속하는 집의 수(크기)를 오름차순으로 나열해서 출력되면 된다.
NxN 격자를 순회하면서 만약 아직 방문하지 않은 집을 발견하면, 그 주변(상하좌우)으로 이어진 모든 1을 하나의 덩어리(단지)로 묶어 표시한다.
BFS나 DFS를 통해 연결된 집들을 전부 방문 처리(0 또는 방문체크)한 뒤, 그 개수를 세어 반환한다.
찾은 단지가 여러 개 나오면, 각각의 집 개수를 기록하고, 정렬하여 출력한다.
[Silver I] 단지번호붙이기 - 2667
나의 풀이
from collections import deque
N = int(input())
graph = [list(map(int, input())) for _ in range(N)]
def bfs(graph,x,y):
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()
queue.append((x,y))
graph[x][y] = 0
cnt = 1
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= N or ny <0 or ny >= N:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx,ny))
cnt += 1
return cnt
count = [bfs(graph, i, j) for i in range(N) for j in range(N) if graph[i][j] == 1]
count.sort()
print(len(count))
for i in range(len(count)):
print(count[i])input()이 '11100'이면 공백이 없어서 '11100' 한 덩어리로 보기때문에 문자를 하나씩 int로 변환해야한다.
input().strip()은 '11100'다. list('11100')은 ['1','1','1','0','0']이 되고 이걸 map(int,['1','1','1','0','0'])라고 해야 ['1','1','1','0','0']형태가 돼서 2차원 배열이 된다!
N → 지도의 크기, graph → NxN 2차원 리스트(각 원소 0/1)
반복문에서 만약 graph[i][j] == 1은 새 단지 시작 -> bfs() 호출하여 연결된 모든 집 방문 & 개수 반환 -> 개수를 counts 리스트에 저장
len(counts) → 전체 단지 수를 정렬 후 출력한다.
이 로직에서 중요한 점은 그래프의 어떤 원소를 방문하면 인접한 1을 모두 탐색하고 그 탐색 범위를 0으로 바꿔서 중복 탐색을 막는다는 것이다.
성능 요약
메모리: 34952 KB, 시간: 60 ms
분류
너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2025년 2월 27일 13:52:58
문제 설명
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
