728x90 반응형 난이도 상1 백준 7576 1. 문제이해 2. 문제분석 (1,1) ~ (M, N) 까지 이중 for문을 돌면서 1(토마토가 익은 지점)이 있으면 그 지점을 기준으로 삼아서 주변에 0(익지 않은 토마토)를 1로 만드는 과정을 수행하면 되는데 익은 토마토로 만드는 과정이 최대 N*M번 수행될 수 있으니 O(N*N*M*M)의 시간복잡도가 걸리게 되어서 시간 내로 해결이 불가능하다. 예시를 들자면 n=2, m=3 일때 토마토가 익은지점까지 찾아가는데 4번(n*m)이 걸리고 토마토가 익은지점에서 인접한 익지 않은 토마토를 큐에 push, pop 해서 모두 익은 토마토로 만드는 과정이 4번(n*m)걸린다. 그래서 1(토마토가 익은)인 지점을 모두 큐에 넣고 BFS를 수행하는 것이다. 그리고 board 배열(익은 토마토, 익지않은 토마토, 벽.. 2024. 4. 20. 이전 1 다음 728x90 반응형
