[C++] 백준 2667번 단지번호붙이기

그래프 이론 문제.

연결 요소(Connected Components)의 개수를 구하고 각 연결 요소에서의 정점의 개수를

오름차순으로 정렬해서 출력하는 문제.

 

연결 요소의 개수는 DFS, BFS로 구할 수 있다. 나는 DFS를 이용해서 해당 문제를 풀었다.

 

문제풀이

사용한 STL과 변수

먼저 입력받는 정수 n, 그리고 지도를 나타내는 2차원 배열 map(1~25의 idx를 사용하기 위해 26의 크기로 만들었다.)

각 연결요소마다 집이 몇 개가 있는지 세기 위해 house_count라는 정수형 변수를 만들었다.

그리고 해당 정점이 이전에 방문했는지 체크하기 위한 bool형 2차원 배열 visit을 만들었다.

house_vec 벡터형 변수로 각 연결요소에서 정점의 개수들을 입력해서 저장했다.

 

DFS 메서드이다. 사실 이 부분에서 실수해서 처음에 틀렸다.

문제의 조건은 상, 하, 좌, 우를 살펴보는 것이다. 따라서 한 정점을 갔을 때 나는 상, 하, 좌, 우로 다시한번 dfs를 호출하면 된다.

이 때 return하는 조건이 있는데,

1. x가(y가) 1보다 작거나
2. x가(y가) n보다 크거나
3. map[x][y]가 0, 즉 해당 지점에 집이 없거나
4. visit[x][y]가 true, 즉 해당 지점을 이미 방문 했었다면

return한다는 조건이다.

나는 여기서 x가 1보다 작거나 y가 n보다 크거나의 조건만 확인했다... 그래놓고 뭐가 틀렸는지 찾아보았다...

상, 하, 좌, 우를 확인하는 문제를 풀 때에는 꼭 1 > x / n < x / 1 > y / n < y의 네 개의 조건을 확인해야 한다.

 

해당 정점을 방문하고 나서는 방문했다고 기록하고 현재 내가 보고있는 단지의 집을 기록하는 변수 house_count에 1을 더해준다.

그리고 상, 하, 좌, 우에 다시한번 dfs 메서드를 호출한다.

 

메인함수 - 1

정수를 입력받는데 문제의 입력을 보면 띄어쓰기로 입력받는 것이 아니라 붙어서 입력을 준다.

따라서 나는 문자열 객체 하나를 만들어서 문자열로 입력받고 문자열의 각 칸마다 '0'을 빼서 0 또는 1로

map 배열에 저장했다.

 

메인함수 - 2

정수를 입력받고 다시한번 이중 포문을 돌면서, 각 칸이 1이면서 방문한 적이 없는 곳은 dfs를 시작한다.

그리고 dfs가 끝나면 house_vec 벡터에 현재 단지의 집의 수를 저장한 house_count의 수를 저장한다.

그리고 다음 단지의 집의 수를 구하기 위해 house_count를 0으로 초기화한다.

 

이중 포문이 끝나면 house_vec 벡터를 오름차순으로 정렬한다.

그리고 맨 처음에 단지의 수는 house_vec 벡터의 사이즈로 출력하고

향상된 for문을 이용해서 단지들의 집의 수를 출력한다.

 

처음에 완벽하게 풀었다고 생각했는데, 아직 디테일적인 부분이 많이 부족한 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드의 전문은 위에서 확인 가능하다.