woon1113   2년 전

틀린 테스트 케이스를 못찾겠어서 어디가잘못됬는지 모르겠네요 ㅜ

첨부터 다시해야하나..

djm03178   2년 전

원인을 한 번 분석해봅시다.

지금 출력을 arr[i]+1로 하고 계신데, 즉 그 말은 arr에 세어진 칸의 개수는 항상 실제 칸보다 1 모자라다는 가정을 하신 거겠죠?

왜 그러냐면 BFS를 처음 시작하는 칸을 세지 않았기 때문입니다.

그리고 시작한 칸을 중복 방문하지 않기 위해서 if (x == 0 || y == 0) { map[x][y] = 1; } 라는 문장을 넣으셨는데, 이 조건이 좀 이상하죠. 왜 x가 0이거나 y가 일 때만 이 처리를 해야 할까요?

간단한 반례로,

3 3 2

0 0 3 1

0 0 1 3

이 경우 남는 칸은 4칸인데, 출력해보면 5칸으로 뜨죠. 그 이유는 BFS가 처음 호출되는 점의 좌표가 y도 x도 0이 아니기 때문에, 다른 칸을 방문했다가 그 칸이 다시 원래의 칸을 또 방문하기 때문에 모든 칸에 대해 arr[cnt]가 증가하기 때문입니다.

woon1113   2년 전

와.. 정말 감사합니다 ㅜ

말씀 하신것처럼 출력을 +1을 해줄필요가 없는 거였네요 BFS함수의 처음 if문을 삭제하고

빈블럭이 하나일 경우에만 arr[cnt]를 1로 설정해주니까 정답되네요 

감사합니다!

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