TIL) BFS 기초 구조 적용하기

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

BFS 탐색

bfs 기초문제를 풀어보면서 bfs의 구조 이해하기

🎢 BFS 기초 구조

✨입력값 받기

• 그래프 받기(2차원)
• 방문 체크용 리스트(2차원)

✨메인 함수

• 모든 노드를 탐색
• 조건 : 그래프의 노드 값이 1이고 방문 체크가 안되어있다면
• bfs 호출

✨bfs함수

• 들어온 노드를 dq에 넣기
• dq에서 pop해서 상하좌우 탐색
  nx, ny를 가지고
  조건) 지도 밖으로 나갔는지, 집이 있는지, 방문한 적 없는 곳인지
  -> dq에 넣고 방문처리 해줌

🎪 문제에 적용하기

백준 2667 단지번호 붙이기 : https://www.acmicpc.net/problem/2667

• 소스코드

import sys
from collections import deque
# import numpy as np
input = sys.stdin.readline

N = int(input())

graph = []

for _ in range(N):
    graph.append(list(map(int, input().strip())))

visited = [[0]*N for _ in range(N)]

cnt = 0 # 단지 수

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
answer = []

def bfs(y, x, cnt):
    count = 0
    dq = deque()
    dq.append((y, x))
    visited[y][x] = 1
    graph[y][x] = cnt
    count += 1

    while dq:
        y, x = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if nx <0 or ny < 0 or nx >= N or ny >= N:
                continue
            if graph[ny][nx] == 0 or visited[ny][nx] != 0:
                continue
            dq.append((ny, nx))
            count += 1
            visited[ny][nx] = 1
            graph[ny][nx] = cnt
    answer.append(count)


# main
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and visited[i][j] == 0:
            cnt += 1
            bfs(i,j,cnt) # 1단지부터 시작

print(cnt)
answer.sort()
for i in range(cnt):
    print(answer[i])