궤도
[백준] 2667번 : 단지번호붙이기 본문
문제
풀이
문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다.
배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다.
bfs, dfs에서 빠져나왔다는 건 더이상 해당 root와 이어진 1이 없다는 뜻이니까 다시 새로운 1이 나올때까지 배열을 돌면 되겠다.
난 그냥 편하게 재귀함수 돌리려고 dfs로 했다.
그나저나 이런 문제를 풀땐 상하좌우로 이동하면서 풀어야 하는데..
아무생각없이 상하좌우로 이동하다간 5x5배열에서 [-1][0]을 참조하거나 [6][2]를 참조하게 될 수도 있다.
이걸 해결하는 방법은 여러가지가 있지만
난 이렇게 상하좌우 테두리를 둘러주는 방법을 선호한다.
위아래 2줄씩 더 생긴다고 큰 일이 일어나진 않을테니까...
소스코드
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[27][27], N, local_cnt;
vector<int> cluster; //각 단지내 집의 수
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우
void dfs(pair<int, int> pos) { //같은 단지에 속한 집을 찾는 dfs
for (int i = 0; i < 4; i++) { //현위치의 상하좌우 좌표를 row, col에 저장
int row = pos.first + dir[i].first;
int col = pos.second + dir[i].second;
if (matrix[row][col] == 1) { //방문한 적 없는 집(leaf)
local_cnt++; //해당 단지의 집의 수 증가
matrix[row][col] = 0; //방문 체크
pair<int, int> next_pos = {row, col};
dfs(next_pos); //재귀 호출
}
}
}
int findHouse() {
int cnt = 0; //총 단지수
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (matrix[i][j] == 1) { //방문한 적 없는 집(root)
cnt++; //총 단지 수 증가
local_cnt = 1;
matrix[i][j] = 0;
pair<int, int> start = {i, j};
dfs(start); //연결된 모든 집을 찾음
cluster.push_back(local_cnt); //단지내 집의 수를 저장
}
}
}
return cnt;
}
int main() {
string tmp;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> tmp;
for (int j = 1; j <= N; j++)
matrix[i][j] = tmp[j - 1] - '0';
}
cout << findHouse() << '\n'; //총 단지수 출력
sort(cluster.begin(), cluster.end()); //정렬
for (int i = 0; i < cluster.size(); i++) //단지별 집의 수 출력
cout << cluster[i] << '\n';
}전체 소스코드다.
//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[27][27], N, local_cnt;
vector<int> cluster; //각 단지내 집의 수
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우최대 입력이 25x25라고 했으니 27x27 크기의 2차원 배열을 선언한다.
전역변수 local_cnt는 dfs를 도는 단지내 집의 수를 저장할 것이다. 그 결과는 cluster에 저장할 것이다.
그리고 상하좌우를 좀 편하게 접근하기 위해 페어 배열 dir를 만들었다.
string tmp;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> tmp;
for (int j = 1; j <= N; j++)
matrix[i][j] = tmp[j - 1] - '0';
}도대체 왜 입력을 띄어쓰기 없이 넣는지 모르겠지만 입력을 받고...
int findHouse() {
int cnt = 0; //총 단지수
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (matrix[i][j] == 1) { //방문한 적 없는 집(root)
cnt++; //총 단지 수 증가
local_cnt = 1;
matrix[i][j] = 0;
pair<int, int> start = {i, j};
dfs(start); //연결된 모든 집을 찾음
cluster.push_back(local_cnt); //단지내 집의 수를 저장
}
}
}
return cnt;
}총 단지 수를 리턴할 findHouse 함수다.
반복문을 돌다가 집을 발견하면 총 단지의 수를 늘려주고 local_cnt를 1로 초기화 한다.(root 집이 있으니까)
matrix[i][j]를 0으로 만들어 방문 표시를 한다. visited를 true로 체크하던 것과 같다.
그리고 이 root 집에 대한 dfs를 호출한다. dfs 후 local_cnt가 바뀌어 있을 것이다. 이를 cluster에 넣어준다.
void dfs(pair<int, int> pos) { //같은 단지에 속한 집을 찾는 dfs
for (int i = 0; i < 4; i++) { //현위치의 상하좌우 좌표를 row, col에 저장
int row = pos.first + dir[i].first;
int col = pos.second + dir[i].second;
if (matrix[row][col] == 1) { //방문한 적 없는 집(leaf)
local_cnt++; //해당 단지의 집의 수 증가
matrix[row][col] = 0; //방문 체크
pair<int, int> next_pos = {row, col};
dfs(next_pos); //재귀 호출
}
}
}재귀함수로 구현한 dfs다. 상하좌우 좌표를 확인하며 집이 있는지 본다.
집을 발견한 뒤 코드 진행은 findHouse에서 집을 발견했을 때와 매우 유사하나,
총 단지 수가 아닌 단지내 집의 수를 늘려준다는 것이 다르다.
cout << findHouse() << '\n'; //총 단지수 출력
sort(cluster.begin(), cluster.end()); //정렬
for (int i = 0; i < cluster.size(); i++) //단지별 집의 수 출력
cout << cluster[i] << '\n';정렬하라고 헀으니까 정렬한 뒤 출력한다.
