반응형
https://www.acmicpc.net/problem/1743
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
소스코드
풀이
★ 주변에 있는 음식물들을 탐색하여 가장 큰 음식물를 찾아내는 전형적인 BFS 문제였던 거 같습니다 !
★ 그래프를 만들 때 시작을 0,0에서 시작하기 때문에 입력받는 x,y 좌표에 각각 -1을 해준 뒤 음식물의 위치라는 것을 1로 표시해줍니다.
★ 그래프를 탐색하면서 해당 좌표가 1일때, 즉 음식물일 때 주변을 탐색하는 BFS를 실행하게 됩니다.
★ 음식물의 크기를 세아릴 cnt는 1부터 시작합니다. 그 이유는 BFS를 시작할 때 이미 음식물 하나를 발견했기 때문입니다 !
★상하좌우를 탐색하며 좌표가 그래프의 범위를 벗어나지 않으면서, visited가 False이면서, 음식물이 있는 위치인 것을 찾아갑니다 !
★ BFS가 끝났을 때 ans에 max(ans,cnt)를 사용해 최대값을 대입해줍니다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1303번: 전쟁 - 전투 (Python, BFS) (0) | 2023.10.16 |
|---|---|
| [백준 알고리즘] 3184번: 양 (Python, BFS) (0) | 2023.10.16 |
| [백준 알고리즘] 2910번: 빈도 정렬 (Python) (0) | 2023.10.04 |
| [백준 알고리즘] 1325번: 효율적인 해킹 (Python, BFS) (0) | 2023.10.02 |
| [백준 알고리즘] 25192번: 인사성 밝은 곰곰이 (Python) (0) | 2023.10.02 |