✅ 문제 링크
https://www.acmicpc.net/problem/1926

✅ 문제 파악
BFS 기본 문제 (❁´◡`❁)
도화지에 1로 연결된 구간(상하좌우)를 한 그림이라고 정의했을 때,
그림의 개수를 구하고, 가장 큰 그림의 넓이를 출력한다. (예외처리 필요)
✅ 접근 방법
visited -> 방문 여부를 확인하기 위한 2차원 배열
dxs, dys -> 상하좌우 방향을 표현하기 위한 리스트
can_go 함수의 조건
1. 주어진 좌표가 그래프 범위 안에 존재해야함
0<=x<n and 0<=y<m
2. 방문하지 않았어야 함
3. graph[x][y] == 1이여야 함
bfs 함수 정의
1. queue를 만들고, 시작 좌표를 큐에 넣는다.
2. 큐가 빌 때까지 다음을 반복
- 큐에서 좌표 (a,b)를 꺼냄
- 상하좌우 방향으로 이동할 좌표(new_x, new_y)를 확인
- 해당 좌표가 can_go 함수에 만족한다면?
-> 방문처리 후 큐에 넣기 !
-> 방문한 노드의 개수(count)를 1 증가
3. 최종적으로 방문한 노드의 개수 반환
최종 !
1. 그래프의 모든 좌표를 순회하면서, can_go에 만족하는 좌표 찾기
2. 해당 좌표에 bfs함수를 호출하여 arr리스트 저장
3. arr리스트의 길이와 최댓값 출력 (arr리스트 길이가 0일 때 예외처리 필요)
✅ 코드 구현
import sys
from collections import deque
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
# 방문 여부 체크 그래프
visited = [[False for _ in range(m)] for _ in range(n)]
# 상하좌우 방향 정의
dxs,dys = [0, 0, 1, -1], [1, -1, 0, 0]
# 주어진 좌표에서 이동할 수 있는지 확인하는 함수
def can_go(x,y):
# 그래프의 범위 내에 있고, 방문하지 않았으며, 값이 1인 경우 True 반환
return 0<=x<n and 0<=y<m and not visited[x][y] and graph[x][y]==1
def bfs(x,y):
count = 1 # 그림 크기 1로 초기화
q = deque()
q.append((x,y)) # 시작 좌표 큐에 추가
while q:
a,b = q.popleft()
for dx,dy in zip(dxs,dys):
new_x, new_y = a+dx, b+dy # 상하좌우 방향으로 이동한 좌표
if can_go(new_x,new_y):
count += 1 # 그림의 크기 증가
visited[new_x][new_y] = True # 방문 처리
q.append((new_x,new_y)) # 큐에 추가
return count # 그림의 최종 크기 반환
arr = []
for i in range(n):
for j in range(m):
if can_go(i,j) :
visited[i][j] = True # 시작 좌표 방문 처리
arr.append(bfs(i,j))
# 그림이 하나도 없는 경우 예외처리
if len(arr) == 0:
print(len(arr))
print(0)
else:
print(len(arr)) # 그림의 개수
print(max(arr)) # 가장 큰 그림
📌배우게 된 점
BFS의 구현 코드를 복습하며, BFS의 초초초초 기본 문제를 구현해보았다 !
조금 더 시간을 들여 공부해야할 것 같다
'[Algorithm] 알고리즘' 카테고리의 다른 글
| [프로그래머스] 네트워크 (Python)(Java) - DFS/BFS (2) | 2024.07.19 |
|---|---|
| [Algorithm] 재귀 함수와 리턴(return) (1) | 2024.07.18 |
| 최소 신장 트리(MST) (1) | 2024.07.09 |
| 이진 탐색 (0) | 2024.07.09 |
| 그래프 (1) | 2024.07.09 |