바킹독 BFS 강의 연습 문제
알고리즘은 알겠는데 적용하는 건 또 다른 문제였다.
BFS 알고리즘을 한 점에서 시작해서 가능한 경로를 찾는 문제에만 적용하는 줄 알았는데, 이번 문제처럼 2중 반복문으로 모든 점을 확인하면서 떨어진 경로에 대한 탐색도 할 수 있다는 걸 알게 되었다.
🦾 배운 점
- 2차원 배열 초기화
# 가로가 m, 세로가 n일 때
visited = [[False] * m for _ in range(n)]def키워드로 함수를 정의할 수 있다.
def bfs(x, y) :
# 함수 정의import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split()) # 세로 n, 가로 m
board = [] # 도화지
for i in range(n) : # 도화지에 그림 입력받기
board.append(list(map(int, input().split())))
# 위, 오른쪽, 아래, 왼쪽 순으로 시계방향 탐색을 도와줄 방향 배열
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 방문한 칸을 표시할 2차원 배열
visited = [[False] * m for _ in range(n)]
# bfs 함수 정의
def bfs(x, y) :
area = 1 # 각 그림의 넓이
q = deque() # bfs 탐색을 도와줄 큐
visited[x][y] = True # 시작 점 방문 표시
q.append((x, y)) # 시작 점을 큐에 넣기
while q : # 큐가 빌 때까지 반복
x, y = q.popleft() # front 제거 (현재 탐색할 칸의 좌표 얻기)
for i in range(4) : # 인접한 네 방향에 대해 반복
nx = x + dx[i] # 다음 x 좌표
ny = y + dy[i] # 다음 y 좌표
# 인덱스가 유요한 범위를 넘어선 경우 continue
if nx < 0 or nx >= n or ny < 0 or ny >= m :
continue
# 인접한 칸이 색칠되어 있고, 아직 방문하지 않은 경우
if board[nx][ny] == 1 and not visited[nx][ny] :
visited[nx][ny] = True # 방문 표시
q.append((nx, ny)) # 큐에 삽입
area += 1 # 그림의 넓이 + 1
return area # 그림의 넓이 반환
cnt = 0 # 총 그림의 개수
max_area = 0 # 가장 큰 그림의 넓이
# 2중 반복문으로 도화지의 모든 칸에 대해 반복
for i in range(n) :
for j in range(m) :
# 현재 칸이 색칠되어 있고 방문하지 않은 경우 bfs 탐색의 시작점
if board[i][j] == 1 and not visited[i][j] :
cnt += 1 # 총 그림 개수 + 1
max_area = max(max_area, bfs(i, j)) # bfs의 반환값과 max_area중 큰 값을 max_area에 저장
# 결과 출력
print(cnt)
print(max_area)
