testcase.ac에 돌려본 결과 다음과 같은 반례가 나왔습니다.
질문과는 상관없는 답이긴 하지만 일단 외부 공기와 갇힌 공기 구별이 잘 되지 않습니다.
질문자분께서는 board[i][j] == 0일 때 상하좌우 중 세 방향에 대해 치즈가 있어야 한다고 가정하고 코드를 짜신 것 같습니다.
그러나 아래 케이스와 같이 치즈가 꼭 세 방향에 대해 없더라도 갇힌 공기가 될 수 있습니다.
이것도 해결하시면 좋을 듯합니다.
2638번 - 치즈
testcase.ac에 돌려본 결과 다음과 같은 반례가 나왔습니다.
질문과는 상관없는 답이긴 하지만 일단 외부 공기와 갇힌 공기 구별이 잘 되지 않습니다.
질문자분께서는 board[i][j] == 0일 때 상하좌우 중 세 방향에 대해 치즈가 있어야 한다고 가정하고 코드를 짜신 것 같습니다.
그러나 아래 케이스와 같이 치즈가 꼭 세 방향에 대해 없더라도 갇힌 공기가 될 수 있습니다.
이것도 해결하시면 좋을 듯합니다.
바깥 공기, 안 공기 같은 것 길게 구현할 필요 없이 while<bfs, N*N 반복문 돌며 치즈 지우기>로 풀 수 있습니다. 바깥에서 bfs, dfs를 돌면 안 공기는 자연스레 방문을 안 하게 되니까 굳이 신경쓸 필요가 없습니다.
어딘가에 오류가 있어서 무한루프가 도는 것같습니다. 아 윗분이 써주셨네요. 안 공기의 정의는 본문의 코드 같은 게 아니라 단순히 바깥에서 bfs로 접근이 불가능한 공기니까요. 정의를 그대로 따라가야합니다
제가 임의로 최대로 큰 테스트케이스를 만들어보았습니다.
답은 97입니다.
보니까 58번부터 69번까지의 while문에서 무한루프가 도는 것 같아요.
1분을 가만히 기다려도 답이 나오지 않았습니다.
만약 위의 문제를 해결하신다면 이 테스트케이스도 사용해보세요.
두 분 좋은 말씀 감사합니다. 스스로의 힘으로 풀어보겠습니다!
댓글을 작성하려면 로그인해야 합니다.
dohyeong0423 1년 전
어디선가 무한루프가 도는 건지, 아니면 순수하게 오래걸리는 건지 잘 모르겠습니다.
추가적으로 현재 로직보다 더 나은 방법이 있는지 궁금합니다.