dohyeong0423   1년 전

어디선가 무한루프가 도는 건지, 아니면 순수하게 오래걸리는 건지 잘 모르겠습니다.

추가적으로 현재 로직보다 더 나은 방법이 있는지 궁금합니다.


hemisphere1357   1년 전

testcase.ac에 돌려본 결과 다음과 같은 반례가 나왔습니다.

질문과는 상관없는 답이긴 하지만 일단 외부 공기와 갇힌 공기 구별이 잘 되지 않습니다.

질문자분께서는 board[i][j] == 0일 때 상하좌우 중 세 방향에 대해 치즈가 있어야 한다고 가정하고 코드를 짜신 것 같습니다.

그러나 아래 케이스와 같이 치즈가 꼭 세 방향에 대해 없더라도 갇힌 공기가 될 수 있습니다.

이것도 해결하시면 좋을 듯합니다.

leeingyun96   1년 전

바깥 공기, 안 공기 같은 것 길게 구현할 필요 없이 while<bfs, N*N 반복문 돌며 치즈 지우기>로 풀 수 있습니다. 바깥에서 bfs, dfs를 돌면 안 공기는 자연스레 방문을 안 하게 되니까 굳이 신경쓸 필요가 없습니다.

어딘가에 오류가 있어서 무한루프가 도는 것같습니다. 아 윗분이 써주셨네요. 안 공기의 정의는 본문의 코드 같은 게 아니라 단순히 바깥에서 bfs로 접근이 불가능한 공기니까요. 정의를 그대로 따라가야합니다

hemisphere1357   1년 전

cheese.txt

제가 임의로 최대로 큰 테스트케이스를 만들어보았습니다.

답은 97입니다.

보니까 58번부터 69번까지의 while문에서 무한루프가 도는 것 같아요.

1분을 가만히 기다려도 답이 나오지 않았습니다.

만약 위의 문제를 해결하신다면 이 테스트케이스도 사용해보세요.

dohyeong0423   1년 전

두 분 좋은 말씀 감사합니다. 스스로의 힘으로 풀어보겠습니다!

jyhan0625   11달 전

바깥에서 bfs하면서 최외각의 치즈를 깎아나가면 풀 수 있으실 겁니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.