BFS로 풀면 되는 문제.
그래프를 양방향 연결해준 뒤, 1번 노드에서 BFS를 돌려 연결된 경우 visit 배열을 True
로 바꿔준다.
2번째 노드부터 visit 배열을 돌면서 만약 값이 참인 경우, 감염된 컴퓨터이므로 그 수를 세어주면 된다.
from sys import stdin
from collections import deque
input = stdin.readline
N = int(input())
edge = int(input())
graph = [[] for _ in range(N + 1)]
for _ in range(edge):
n1, n2 = map(int, input().split(" "))
# 양방향 연결
graph[n1].append(n2)
graph[n2].append(n1)
visit = [False for _ in range(N + 1)]
def bfs(start):
q = deque([start])
visit[start] = True
while q:
node = q.popleft()
for next_node in graph[node]:
if not visit[next_node]:
visit[next_node] = True
q.append(next_node)
bfs(1)
answer = 0
for i in range(2, N + 1):
if visit[i]:
answer += 1
print(answer)
BFS로 풀면 되는 문제.
그래프를 돌면서 상하좌우로 값이 1인 경우, 집이 있는 곳이므로 해당 구역의 크기를 체크한다.
방문 처리용 배열을 따로 두지 않고, 만약 방문한 경우 그 값을 2로 바꿔 방문처리를 체크했다.
구역의 크기를 배열로 저장한 뒤, 배열의 길이와 배열을 오름차순으로 정렬한 결과를 출력해주면 된다.
from sys import stdin
from collections import deque
input = stdin.readline
N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]
# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
def bfs(sr, sc):
q = deque([(sr, sc)])
count = 1
graph[sr][sc] = 2 # 방문처리
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N:
if graph[nr][nc] == "1":
count += 1
graph[nr][nc] = 2 # 방문처리
q.append((nr, nc))
return count
answer = []
for r in range(N):
for c in range(N):
if graph[r][c] == "1":
answer.append(bfs(r, c))
print(len(answer))
answer.sort()
for num in answer:
print(num)