BOJ 백준 2667번 단지번호붙이기 | Python
🔎 문제 설명
🩶 실버 1
- 난이도 ★☆☆☆
- 그래프탐색 BFS
기본적인 그래프탐색 문제로, 풀이는 어렵지 않다. 마지막 문제 조건을 빼먹지 말자!
각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력
📌 문제 풀이 큰 틀
- 집을 방문하면 노드 값
0으로 업데이트 - 단지 번호 수를 리스트로 저장
💻 내 코드
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
town = [list(map(int, list(input().strip()))) for _ in range(N)]
def bfs(x, y):
queue = deque([(x,y)])
town[x][y] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
cnt = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<= nx <N and 0<= ny <N:
if town[nx][ny]:
town[nx][ny] = 0
queue.append((nx,ny))
cnt += 1
return cnt
ans_cnt = []
for i in range(N):
for j in range(N):
if town[i][j]:
ans_cnt.append(bfs(i, j))
print(len(ans_cnt))
for ans in sorted(ans_cnt):
print(ans)
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).