heroswift15   5년 전

BFS 이용

입력이 주어지면 전체 맵의크기가 기껏해야 25 밖에 되지 않으므로 1 과 0으로 이루어진 map 2차원 배열을 이용하여 설계했습니다.

   첫번째배열 (0,0) 부터 탐색을 해주었습니다 .탐색과정에서 이미 방문하여 cabbage 의값이 1 일경우 pass 또는 map 값이 0

일 경우에도 pass 해주었고 그과정에서 탐색 영역이 끝날때마다 bug 개수를 카운트 해주었습니다 .그리고  그값은 

헤당 케이스 내에서 출력되도록 차례차례 출력해 주었고 전체  배추 밭에서 배추가 0개 있을 경우도 있을수 있으니 chk를 통해서 해결해주었습니다.

하지만 결과는 틀렸습니다.... 예제와 질문 게시판에 올라와있는 반례를 해보았습니다 .모두 정상적인 답이 나왔는데. 

혹시 제가 잘못 짚고 가는 부분이  있는지에 대해 질문 드립니다.ㅠㅠㅠ

감사합니다.!!


heroswift15   5년 전

원인은 아주 작은 아니 작지않은 큰 실수에 있었습니다. 이문제 는 반복문 안에서 즉석(?) 으로 그떄그때 케이스의 값을 입력 받아서 문제 해결을 요구하고 있습니다.

본인은 BFS를 이용하여 풀기위해 queue 라는 구조체 를 이용했습니다. 하지만 본인은 입력이 기하적으로 증가 한다는 것을 망각하고 front와 rear를 매 케이스가 끝날떄마다

초기화 해주는것을 하지 못하였습니다. 뿐만 아니라 . row 와 col 또한 구조체에 값을 저장하여 입력 받았습니다 .그결과 이또한 위와 같은 이유로  통과하지 못했습니다.

매 순간마다 구조체를 0으로 초기화 하는 비용이 아까워 쉽게 x,y 로 바꿔 주었고  row와 col 이 있는 구조체는 삭제 했습니다.

군대에서 공부하기 힘드네...

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