[백준][search] 2667 : 단지번호붙이기

문제

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

필요 지식

 - DFS,BFS 개념 

해결 방법

판매상 입장에서 생각해보자.

처음에 판매상은 전체 지도를 모르기 때문에 구역 내를 "순서대로" 다 돌아보려고 할 것이다. 

또, 여기는 판매를 위해 간 곳인지 체크도 해야한다.

사람이 살지 않는 구역을 지나 판매상이 처음으로 집을 찾게 된다면, 분명 가까운 곳에 옆집이 있을 것이라 생각한다. 

즉, 단지가 있을 것이라고 생각한다.

그래서, 사람이 사는 집을 중심으로 상,하,좌,우를 탐색한다. 

탐색 후, 가까운 곳에 사람이 산다면, 그 곳으로 또 가서 같은 방법으로 탐색한다.

단지 내의 집의 수는 한정적이므로, 결국 한 단지 내의 집을 다 돌게 되었을 때에는 다시 다른 단지를 찾아 떠나야 한다.

다른 단지를 찾아 떠날 때에는, 현재 단지 내의 마지막 집에서 찾는 것 보다는 제일 처음에 단지의 첫집에서 출발하는 것이 유리하다.

왜냐하면, 단지 내 마지막 집이 전체 지도 상에서 어느 위치인지 모르지만, 제일 처음에 찾은 집은 방문을 체크하며 걸었기에 현재 위치가 어디인지 아니깐.

그래서 다시 제일 첫 집으로 돌아가 또 순서대로 방문해 본다. 그 후, 또 집을 찾았다면 위의 과정을 반복한다.

이렇게 돌면서 판매상은 자신이 발로 직접 뛴 전체 지도를 완성하게 되고, 단지 내의 집 수도 알 수 있게 된다.

---------------------------------------------------------------------------------------------------

이것을 코드로 옮기게 된다면,

main함수에서 판매자가 순차적으로 도는 것과 순차적으로 돌 때, 집을 찾았다면 bfs나 dfs함수로 주변 탐색 시작을 구현해야 한다.

dfs나 bfs함수에서는 상,하,좌,우를 탐색해야 한다.

탐색하며, 방문하지 않았던 곳이고, 집도 있는 곳이라면 또 그 곳에 가서 상,하,좌,우를 탐색한다.

나는 재귀dfs로 구현했다. 다 탐색하고 난 다음 재귀로 처음 집을 찾았던 장소로 갈 수 있기 때문이다.

코드