문제
1000x1000 이하의 격자에 상하좌우 방향이 적혀있다. 이 중 최소한의 지점에 safezone을 만들어 모든 노드가 safezone으로 들어오게 해야한다.
이해
격자를 그래프로 본다면, 시작 지점을 먼저 잡는게 우선일 것이다. in degree가 0인 노드를 찾는다. 이 시작 노드들 부터 트리를 그려나간다면 다음과 같은 기준으로 safe zone을 잡을 수 있다.
- 사이클이 존재하면 안된다.
사이클이 존재한다면, 결국 safe에 못들어가고 뺑뺑이 돌것이다.
- 각 트리의 최상단 루트는 safe여야한다.
더 이상 갈 곳이 없는 최상단 노드(바깥을 바라보고 있는 노드)는 safe여야한다.
알고리즘
-
시작 노드들을 찾는다. start[]
-
자신에 연결된 노드들을 순회하며 사용된 노드인지 기록하면서 탐색한다 used[x][y] = cluster 인덱스
-
사이클이 발생했거나 outdegree가 0인 노드를 만난다면 해당 노드를 safezone으로 추가한다.
사이클은 아니지만 used가 존재한다면 스킵한다.
정당성 검증
Q1 사이클 중 아무 노드를 고르더라도 safe의 최소성을 보장할 수 있는가
그렇지 않다면, 하나의 safe 노드로 두개 이상의 클러스터 (사이클 또는 트리)를 해결 할 수 있어야 한다. 하지만 하나의 칸에는 하나의 방향만 존재하기 때문에 한지점에서 두개의 길로 나뉘는 분기점은 존재하지 않는다.
Q2 사용여부는 클러스터 내에서 기준인지, 아니면 전역으로 할건지
used[x][y] = 클러스터의 인덱스. 로 하려고 함. 개별 클러스터의 used를 관리해서 같은 클러스터의 격자를 다시 만나면 사이클을 판별할 수 있지만, 다른 클러스터 사이의 이미 safezone이 확보된 곳인지는 알 수 없음.
그래서 클러스터의 index를 저장한다면, 동일한 클러스터의 사이클 여부를 확인할 수 있으며(현재 진행중인 인덱스와 같은지), 이미 safezone이 확보된 클러스터를 만난 것인지 확인 할 수 있다.(다른 인덱스를 만난다면, 해당 클러스터로 편입해서 진행하면 된다. ) 좀더 자세히 말하자면, 다른 인덱스를 만난다면, 해당 클러스터는 무조건 safezone을 찾았을 수 밖에 없다. 만나는 노드가 진입노드여서 아직 탐색을 진행하지 못한 경우가 있지 않을까 했지만, 이는 진입노드의 정의에 위배된다. 서로 재귀적으로 ‘쟤가 해결해주겠지’와 같은 문제도 발생 할 수 없다. 한놈은 safezone에 붙어있어야 한다.
Q3. 독립된 사이클은 어쩔래
2번 문제를 고민하다가, 내 알고리즘의 허점을 발견했다. 아직 다른 노드들과 진입/진출이 전혀 없는 독립된 사이클은 해결하지 못한다는 것을 깨달았다. 이 사이클에 존재하는 노드들은 진입차수가 0이 아니기 때문에, queue에 들어오지 못했고, 이 사이클로 들어오는 방향 또한 존재하지 않기 때문에 다른 노드에 의해 해결되지 않는다.
Q4. 더이상 소외된 노드는 없는가
한번 데이고 나니까 더 조심스러워졌다. 독립된 사이클을 해결하고, 진입차수가0인 애들부터 탐색을 다한다면, 모든 노드를 다 탐색했다고 할 수 있는가. 아직까진 그런 듯 하다.
독립된사이클의 개수 +해주기
3번 질문의 해결책은 기존의 풀이에서 아직 사용되지 않은 노드들을 대상으로 독립된 사이클의 개수를 필요한 safezone의 개수에 더해주면된다. 각각의 사이클은 하나의 safezone이 필요하기 때문이다.
- for for 로 모든 노드 탐색
used가 0이라면, 사이클 탐색 시작. 신규 cluster id 발급. safezone++
- 현재노드를 cluster id 로 used 설정. 다음노드 탐색.
- 다음노드의 cluster id가 현재 노드와 같을때까지 반복.
code
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;
pair<int,int> getNextNode(int i, int j, char arrow){
switch (arrow) {
case 'U': return make_pair(i - 1, j);
case 'D': return make_pair(i + 1, j);
case 'L': return make_pair(i, j - 1);
case 'R': return make_pair(i, j + 1);
default: return make_pair(-1, -1); // Invalid direction
}
}
int main() {
//=== Declare & Input ===
int n,m,k,ans;
string s;
cin>>n >> m ;
vector<vector<char>> v(n+3, vector<char>(m+3) );
vector<vector<int>> in(n+3,vector<int>(m+3, 0));
for(int i=1; i<= n; i++){
cin >> s;
for(int j = 1 ; j <= m; j++){
v[i][j]= s[j-1];
auto [y,x] = getNextNode(i,j,v[i][j]);
in[y][x]++;
}
}
for(int i=0; i< n+3; i++){
v[i][0] = v[i][m+1] = 'x';
}
for(int i=0; i< m+3; i++){
v[0][i] = v[n+1][i] = 'x';
}
// === Logic ===
queue<pair<int,int>> q;
vector<vector<int>> used(n+3,vector<int>(m+3, 0));
int cluster_idx = 1;
int safe = 0;
// 진입차수가 0인 노드 집합 찾기
for(int i=1; i<= n; i++){
for(int j = 1 ; j <= m; j++){
if(in[i][j] == 0) {
q.push(make_pair(i,j));
used[i][j] = cluster_idx++;
}
}
}
// 진입차수가 0인 노드 클러스터 탐색
while(!q.empty()){
auto [cy,cx] = q.front(); q.pop();
while(true){
auto [ny,nx] = getNextNode(cy,cx,v[cy][cx]);
// 외부로 나간 경우
if(v[ny][nx] == 'x' ){
safe++;
// v[cy][cx] = safezone;
break;
}
// 진행중 사이클이 발생한 경우
else if(used[ny][nx] == used[cy][cx] ){
safe++;
// v[cy][cx] = safezone;
break;
}
// 다른 클러스터를 발견한 경우
else if(used[ny][nx] != 0 ){
break;
}
used[ny][nx] = used[cy][cx];
cy = ny; cx = nx;
}
}
// 독립 사이클을 찾는 로직
for(int i=1; i<= n; i++){
for(int j = 1 ; j <= m; j++){
int cy,cx;
if(used[i][j] == 0){
cy = i; cx = j;
safe++;
used[cy][cx] = cluster_idx++;
while(1){
auto [ny,nx] = getNextNode(cy,cx,v[cy][cx]);
if(used[ny][nx] == used[cy][cx]) break;
used[ny][nx] = used[cy][cx];
cy = ny; cx = nx;
}
}
}
}
cout<< safe;
return 0;
}
0개의 댓글
