문제
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
유사한 문제를 이미 풀어본 적이 있다.
BFS문제였다. 다만, 탐색을 시작할 좌표(g[i][j] == 1)가 여러 개이기 때문에 탐색을 시작하기 전에 이 좌표들을 모두 큐에 담아주는 것이 중요했다. 좌표를 모두 큐에 담지 않으면 최적해를 구할 수 없다. 처음 입력을 받을 때부터 큐에 담아주면 좀 더 빠르게 탐색을 진행할 수 있다.
코드
'CS > 알고리즘 문제 풀이' 카테고리의 다른 글
| [백준] 1759 - 암호 만들기 [Python(파이썬)] (0) | 2021.06.10 |
|---|---|
| [백준] 1697 - 숨바꼭질 [Python(파이썬)] (0) | 2021.05.29 |
| [백준] 2178 - 미로탐색 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2667 - 단지번호붙이기 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2606 - 바이러스 [Python(파이썬)] (0) | 2021.05.23 |
문제
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
유사한 문제를 이미 풀어본 적이 있다.
BFS문제였다. 다만, 탐색을 시작할 좌표(g[i][j] == 1)가 여러 개이기 때문에 탐색을 시작하기 전에 이 좌표들을 모두 큐에 담아주는 것이 중요했다. 좌표를 모두 큐에 담지 않으면 최적해를 구할 수 없다. 처음 입력을 받을 때부터 큐에 담아주면 좀 더 빠르게 탐색을 진행할 수 있다.
코드
'CS > 알고리즘 문제 풀이' 카테고리의 다른 글
| [백준] 1759 - 암호 만들기 [Python(파이썬)] (0) | 2021.06.10 |
|---|---|
| [백준] 1697 - 숨바꼭질 [Python(파이썬)] (0) | 2021.05.29 |
| [백준] 2178 - 미로탐색 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2667 - 단지번호붙이기 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2606 - 바이러스 [Python(파이썬)] (0) | 2021.05.23 |
