백준 3184 양

목표: 백준 온라인 저지 3184 양 문제 풀기

환경: mac OS Mojave 10.14, CLion

로직

문제는 울타리(#)와 배열의 범위내에서 구분된 영역을 동서남북 방향으로 탐색한다. 탐색하면서 알아낸 늑대 수와 양의 수를 비교하여 둘중 하나를 제거해주면서 최종적으로 남은 늑대 수 와 양의 수를 출력한다.

BFS 정의: 연결된 정점을 한 번씩 방문한다. 단 인접한 노드들을 우선 모두 방문하면서 뻗어나간다.

입력범위 3<= 행, 열 <= 250

우리는 2중 for문을 통해 2차원 배열(행,열) (0,0) 인덱스부터 (249, 249)까지 반복하면서 빈칸일때마다 BFS를 통해 연결된 정점을 한 번씩 방문한다.

시간복잡도: O(N^2) + O(V+E) 250^2 * 결국 2차원 배열 전체를 방문할 것이기 때문에 250^2 총 30억이라는 큰 시간복잡도가 나옵니다. 실제로는 2차원 배열 전체 중 벽은 제외해야되며, 방문했던 곳은 또 방문하지 않기 때문에 이것보다 훨씬 적은 시간복잡도가 나올 것입니다.

시간복잡도를 줄이기 위해서 BFS를 시작하기 위한 조건을 방문하려는 칸에 늑대 또는 양이 있어야함으로 바꿈으로서 시간복잡도를 줄일 수 있다고 생각했습니다.

SourceCode