[TIL] 2023-09-03 코테 (그래프 2문제)

thousand_yj·2023년 9월 4일
0

TIL

목록 보기
7/14

그래프

실버3. 백준 2606 바이러스

풀이

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)

실버1. 백준 2667 단지번호이어붙이기

풀이

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)
profile
함께 일하고 싶은 개발자가 되기 위해 노력합니다. 코딩테스트 관련 공부 및 이야기는 티스토리에도 업로드되어 있습니다.

0개의 댓글