피리부는사나이[BOJ16724]

Yejun Cheon·2023년 11월 29일
0

Algorithm

목록 보기
1/7

문제

1000x1000 이하의 격자에 상하좌우 방향이 적혀있다. 이 중 최소한의 지점에 safezone을 만들어 모든 노드가 safezone으로 들어오게 해야한다.

이해

격자를 그래프로 본다면, 시작 지점을 먼저 잡는게 우선일 것이다. in degree가 0인 노드를 찾는다. 이 시작 노드들 부터 트리를 그려나간다면 다음과 같은 기준으로 safe zone을 잡을 수 있다.

  1. 사이클이 존재하면 안된다.

사이클이 존재한다면, 결국 safe에 못들어가고 뺑뺑이 돌것이다.

  1. 각 트리의 최상단 루트는 safe여야한다.

더 이상 갈 곳이 없는 최상단 노드(바깥을 바라보고 있는 노드)는 safe여야한다.

알고리즘

  1. 시작 노드들을 찾는다. start[]

  2. 자신에 연결된 노드들을 순회하며 사용된 노드인지 기록하면서 탐색한다 used[x][y] = cluster 인덱스

  3. 사이클이 발생했거나 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이 필요하기 때문이다.

  1. 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;
}
profile
코린이지만 공부중입니다

0개의 댓글