728x90
< 문제 >
< 풀이 >
코드 변수 정의
- graph : 아파트(1)가 표시된 지도
- cnt : 현재 단지 내 아파트 수
- dx, dy : 상하좌우를 탐색할 변수. 상(-1, 0), 하(1,0), 좌(0,-1), 우(0,1)
- nx, ny : 현재 위치에서 상하좌우로 이동했을 때의 좌표
- apartment : 각 단지의 아파트 수를 저장할 리스트
BFS
시간복잡도 : O(N^2)
from collections import deque
# BFS를 이용하여 연결된 아파트 단지의 크기를 계산하는 함수
def bfs(graph, i, j, visited):
q = deque([(i, j)]) # 큐에 시작 좌표(i, j)를 추가
cnt = 1 # 현재 단지 내 아파트 수 (초기값=1, 시작점 포함)
while q:
x, y = q.popleft()
visited[x][y] = True # 현재 위치 방문 처리
# 현재 위치에서 상하좌우 탐색
for dx, dy in [(-1,0), (0,1), (1,0), (0,-1)]:
nx, ny = x + dx, y + dy
# 새로운 위치가 유효한 범위 내에 있고, 방문하지 않았으며 아파트가 있는 경우
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and graph[nx][ny] == '1':
visited[nx][ny] = True # 방문 처리
q.append((nx, ny)) # 큐에 새로운 위치 추가
cnt += 1 # 단지 내 아파트 수 + 1
return cnt # 같은 단지 내 아파트 수 반환
def f():
global N # 전역변수 N (그래프의 크기)
N = int(input())
graph = [input() for _ in range(N)]
visited = [[False] * N for _ in range(N)] # 방문 여부 확인 배열
apartment = [] # 각 단지의 아파트 수를 저장할 리스트
for i in range(N):
for j in range(N):
# 방문하지 않은 아파트를 단지 내 아파트 탐색 시작점으로
if graph[i][j] == '1' and not visited[i][j]:
apartment.append(bfs(graph, i, j, visited))
apartment.sort() # 단지 크기 오름차순 정렬
print(len(apartment)) # 단지 총 개수 출력
print(*apartment, sep='\n') # 각 단지의 크기를 줄바꿈으로 출력
f()
풀이 방식
- 그래프 탐색
- 2중 for문으로 그래프의 모든 위치를 순회한다.
- 현재 위치가 아파트('1')면서, 방문하지 않은 경우 → BFS를 수행하여 단지를 탐색한다.
- BFS로 단지 탐색
- BFS 시작 위치 : (i, j)
- 시작 위치를 기준으로 연결된 모든 '1'을 탐색한다.
- 작동 방식
- 시작 위치를 큐에 추가하고, 방문 처리(visited=True)한다.
- 큐에서 현재 위치를 꺼내고, 상하좌우로 인접한 좌표를 확인한다.
- 인접한 좌표가 그래프 내에 있으며 방문하지 않은 아파트('1')인 경우 큐에 추가하고 방문 처리한다.
- 탐색이 끝날 때까지 연결된 모든 '1'을 확인하고, 단지의 크기(cnt)를 계산한다.
- 단지 크기 저장
- BFS 함수가 반환한 단지 크기를 apartment 리스트에 추가한다.
- apartment를 오름차순으로 정렬한다.
< 회고 >
🤔 💭_
오름차순 정렬(문제 조건 잘 읽기..)
인접한 아파트를 탐색하는 문제여서 bfs로 구현했다.
BFS 말고 다른 풀이 방식이 있을까?
DFS(깊이 우선 탐색)
- 재귀 호출로 연결된 모든 노드를 탐색
def dfs(graph, x, y, visited):
visited[x][y] = True
cnt = 1 # 현재 위치 포함
for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and graph[nx][ny] == '1':
cnt += dfs(graph, nx, ny, visited) # 연결된 노드 탐색
return cnt
def f():
global N
N = int(input())
graph = [input() for _ in range(N)]
visited = [[False] * N for _ in range(N)]
apartment = []
for i in range(N):
for j in range(N):
if graph[i][j] == '1' and not visited[i][j]:
apartment.append(dfs(graph, i, j, visited))
apartment.sort()
print(len(apartment))
print(*apartment, sep='\n')
f()- 재귀 호출로 인한 스택 사용량 증가
- python 기본 재귀 깊이 제한에 주의 (sys.setrecursionlimit)
Union-Find (Disjoint Set Union)
- 그래프의 각 노드를 하나의 집합으로 간주하고, 연결된 노드를 하나의 집합으로 합친다.
- 모든 노드를 순회하며 집합을 합친 후, 각 집합의 크기를 계산한다.
# 부모 노드를 찾는 함수 (경로 압축)
def find(parent, x):
# x의 부모가 자기 자신이 아니라면, 재귀적으로 루트 노드를 찾음.
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 루트 노드로 바로 연결
return parent[x]
# 두 집합을 병합하는 함수 (Union by Rank)
def union(parent, rank, a, b):
# 두 노드 a, b의 루트 노드를 찾음.
rootA = find(parent, a)
rootB = find(parent, b)
if rootA != rootB: # 두 노드가 속한 집합이 다르면 합침.
# rank가 더 큰 쪽이 부모가 됨.
if rank[rootA] > rank[rootB]:
parent[rootB] = rootA
elif rank[rootA] < rank[rootB]:
parent[rootA] = rootB
else: # rank가 같다면 한쪽을 부모로 설정하고 rank + 1
parent[rootB] = rootA
rank[rootA] += 1
def f():
N = int(input())
graph = [input() for _ in range(N)]
# union-find 구조 초기화
parent = {} # 각 노드의 부모 노드
rank = {} # 각 노드의 rank (트리 높이)
node_mapping = {} # 좌표를 노드 번호로 매핑
idx = 0 # 노드 번호
# 그래프의 각 좌표에 대해 노드 번호를 부여하고 초기화
for i in range(N):
for j in range(N):
if graph[i][j] == '1': # 아파트인 경우
node_mapping[(i, j)] = idx # 좌표를 노드 번호로 매핑
parent[idx] = idx # 초기에는 자기 자신이 부모
rank[idx] = 0 # 초기 rank=0
idx += 1
# Union 연산
for (x, y), id1 in node_mapping.items():
for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]: # 상하좌우 탐색
nx, ny = x + dx, y + dy
if (nx, ny) in node_mapping: # 인접 노드가 아파트인 경우
id2 = node_mapping[(nx, ny)]
union(parent, rank, id1, id2) # 두 노드 병합
# 모든 노드의 루트 노드를 찾고, 루트별 노드 수 계산(counter 사용)
from collections import Counter
root_count = Counter(find(parent, node) for node in parent)
# 결과 출력
sizes = sorted(root_count.values())
print(len(sizes))
print(*sizes, sep='\n')
f()- 추가로 부모 및 순위 정보 저장을 위한 메모리 필요
- 연결 관계를 효율적으로 관리하는 데 적합하지만, 구현이 더 복잡
Flood Fill
- DFS와 유사하지만, 방문한 위치를 특정 값으로 변경하여 추가 배열을 사용하지 않는다.
- 그래프를 직접 수정하며 탐색하므로 메모리를 절약할 수 있다.
def flood_fill(graph, x, y):
stack = [(x, y)]
size = 0
while stack:
cx, cy = stack.pop()
if graph[cx][cy] == '1': # 방문 확인
graph[cx][cy] = '0' # 방문 처리
size += 1
for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]: # 상하좌우 탐색
nx, ny = cx + dx, cy + dy
if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == '1':
stack.append((nx, ny))
return size
def f():
global N
N = int(input())
graph = [list(input()) for _ in range(N)] # 문자열을 리스트로 변환
apartment = []
for i in range(N):
for j in range(N):
if graph[i][j] == '1':
apartment.append(flood_fill(graph, i, j))
apartment.sort()
print(len(apartment))
print(*apartment, sep='\n')
f()- visited 배열 대신 그래프를 직접 수정하여 메모리 절약
방식 비교
| 방식 | 시간복잡도 | 공간복잡도 | 특징 |
| BFS | O(N^2) | O(N^2) | 구현 간단 |
| DFS | O(N^2) | O(N^2) | 재귀 호출 |
| Union-Find | O(N^2 * ⍺(N^2)) | O(N^2) | 연결 관계 관리에 효율적 |
| Flood Fill | O(N^2) | O(N^2) | 그래프 수정 |
728x90
'coding_test > 항해99 코테스터디 TIL' 카테고리의 다른 글
| 99클럽 코테 스터디 _ 10일차 TIL (BFS) (0) | 2025.01.24 |
|---|---|
| 99클럽 코테 스터디 _ 9일차 TIL (이분 그래프, BFS) (0) | 2025.01.23 |
| 99클럽 코테 스터디 _ 7일차 TIL (BFS) (0) | 2025.01.21 |
| 99클럽 코테 스터디 _ 6일차 TIL (DFS, BFS) (0) | 2025.01.20 |
| 99클럽 코테 스터디 _ 5일차 TIL (투 포인터) (0) | 2025.01.17 |