토마토
BOJ 7576 토마토
boj 7576 토마토 BFS로 풀 수 있는 문제다. 조금 독특한 점은 시작점이 여러 곳이 될 수 있다는 것이다. 전체를 다 돌아보고 시작점이 될 수 있는 곳을 다 찾아 한번씩 bfs를 다 돌려보는 풀이가 가장 먼저 생각났지만, 최대 시간복잡도가 O((NM)^2)이 될 수 있어 이 방법으론 풀 수 없다. 그래서 토마토 정보를 입력받을 때, 익은 토마토의 시작점을 전부 큐에 넣어주고 bfs를 돌리는 방식으로 문제를 풀었다. 익은 토마토의 경우 거리 dis 값이 전역변수이니 0으로 채워지고, 안 익은 토마토는 dis 값을 -1로 둔다. 코드를 한번 보자. #include #include #include #include using namespace std; int n, m; int board[1005][100..