반응형
https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로
www.acmicpc.net
소스코드
풀이
★ 해당 좌표가 1이라면 상하좌우를 탐색하며 같은 1을 찾아나가는 전형적인 BFS 문제입니다.
★ 이중 반복문을 돌면서 해당 좌표의 값이 1이라면 그림이 그려져있는 것이기 때문에 BFS를 시작해줍니다.
★ 해당 좌표를 중복으로 탐색하지 않기 위해서 그 값을 1에서 0으로 바꿔줍니다. 그 후 상하좌우를 탐색하며 주변에 1을 가지고 있는 값들을 찾아갑니다. 이 때 값을 찾아서 다시 dq에 저장하는 과정을 반복할 때 count값을 1씩 올려줘서 그림의 크기를 확인합니다.
★ while문이 끝났을 경우 더이상 가까이 있는 1이 없으며 그림이 완성된 경우이기 때문에 count를 result 리스트에 넣어줍니다.
★ BFS를 호출할 때마다 cnt를 1씩 증가시키는데, 이는 그림의 갯수입니다. result 리스트 안에 들어있는 값들은 그림의 크기이기 때문에 리스트의 최대값이 가장 넓은 그림이 됩니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1325번: 효율적인 해킹 (Python, BFS) (0) | 2023.10.02 |
|---|---|
| [백준 알고리즘] 25192번: 인사성 밝은 곰곰이 (Python) (0) | 2023.10.02 |
| [백준 알고리즘] 2606번: 바이러스 (Python) (0) | 2023.09.22 |
| [백준 알고리즘] 1202번: 보석 도둑 (Python) (2) | 2023.08.23 |
| [백준 알고리즘] 19638번: 센티와 마법의 뿅망치 (Python) (2) | 2023.08.22 |