[BOJ]2636:치즈

1차 시도)

혹시 시간초과가 날까봐 한번에 bfs를 처리하려고 욕심을 부렸다.

1. 초기 외부 공기 좌표를 모두 큐에 삽입

2. bfs로 탐색

 2-1) 치즈를 만나는 경우 이전 visited[nx][ny]=visited[x][y]+1 처리. 

 2-2) 구멍을 만나는 경우 새로운 큐(holeQueue)에 구멍 좌표를 넣고 새로운 큐에 대해 bfs 탐색

 

그런데 아무리 해도 틀렸다라는 답이 나오고 반례 생각하는데에 시간을 너무 많이써서 새로운 방법으로 다시 풀었다.

 

2차 시도)

1. 좌표가 0이 아닌 값으로 초기의 치즈 갯수 모두 카운트

2. 치즈가 모두 사라질때까지 (0,0)을 큐에 삽입하여 bfs탐색

 

시간초과가 안나다니 행복하다

github.com/SuyeonChoi/Algorithms/commit/c44013e99b111b2e8e80e92c766d8b9835cde083

치즈 using BFS · SuyeonChoi/Algorithms@c44013e

 

코테때 시간이 너무 부족하다..

새로운 솔루션을 시간내에 다시 짜내보려고 노력해봐야겠다