[알고리즘] 백준 2667번

[알고리즘] 백준 2667번

문제

https://www.acmicpc.net/problem/2667

---

풀이

안녕하세요. 오늘도 역시 비교적 쉬운 BFS 문제를 풀어보았습니다. 정답률이 39%이지만 BFS, DFS 문제들 중에서 유명한 문제에 속하기 때문에 정답률은 중요하지 않다고 생각합니다. 기본적으로 저는 로컬에서 풀었을 때는 맞췄으나 사이트에서 채점을 하면 런타임 에러가 몇번 나왔습니다. 이유를 몰랐으나 질문 게시판에서 답글을 보고 무엇이 틀렸는지 이해했으며 초반 코드는 메모리 낭비도 심했기에 이를 보완하기 위해 코드를 약간 개선하였습니다.

저의 풀이 과정은 다음과 같습니다.

1. 먼저 여타 다른 BFS문제와 마찬가지로 방문을 했냐와 안했냐가 기본으로 들어갔습니다.
2. 인접한 1들의 값을 BFS로 찾아가며 방문을 표시하며 영역을 넓혀갔습니다. 인접한 영역을 찾아가며 영역의 넓이를 계산하였습니다.
3. 그리고 나뉘어진 영역의 갯수 또한 하나의 영역의 BFS 탐색이 끝나면 증가시켰습니다.

아래는 제가 최종 작성한 코드입니다. 전체적인 코드는 제가 지금까지 풀었던 BFS코드와 유사한 면이 많습니다.

• 저는 처음에 계산된 영역의 넓이를 담아줄 자료구조로 일반 배열을 선택했고 나뉘어진 영역의 갯수는 N보다 클 가능성도 많기 때문에 int count[] = new int[N*N]과 같이 선언하였습니다. 하지만 이렇게 선언하면 낭비되는 공간이 많기 때문에 List와 ArrayList를 생각하였고 이를 이용해 넓이를 저장하였습니다.

하지만 채점시에는 N*N 배열을 선언했을 때보다 많은 메모리를 사용하는 것을 확인할 수 있었습니다. 이에 대해서는 아직은 저도 의문인 부분입니다. 혹시 이유를 아시는 분은 댓글로 알려주시면 감사하겠습니다.