BFS1 [백준]BOJ 1012 유기농 배추(자바/BFS/메모리 초과) 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 위의 문제 조건을 처음 보았을때 BFS로 풀 수 있겠다고 생각했습니다. 서로 인접해있는 배추 그룹이 몇 그룹이 존재하는지를 알게되면 그건 곧 지렁이 개수를 구하는 것과 다름이 없다고 생각했습니다. 아래 그림과 같이 인접한 배추들을 그룹으로 묶어보면 총 5그룹이 나오는 것을 확인해볼 수 있었습니다. 저는 BFS로 탐색을 수행하며 인접한 배추들에 대해 방문처리를 진행했습니다. 그러나, 메모리 초과라는 문제가 발생했습니다. 결론부터 말씀드리자면 메모리 초과의 원인은 바로 방문처리 문제였습니다!!! 항상 습관처럼 방문체크는 큐에서 pop한뒤 수행했.. 2022. 12. 31. 이전 1 다음
