BOJ 16724

07 Mar 2020 • ProblemSolving

피리 부는 사나이

문제출처

문제 해석

  • 성우가 정해놓은 방향으로 이동하는 맵이 있을 때, 사이클을 없앨 수 있는 최소의 SAFE ZONE 개수를 구하는 문제입니다.

설계(10)

  • 처음에 이 문제를 보았을 때, union-find 기법을 응용한 문제라고 생각했습니다.
  • 그러나, 어떻게 적용할지 생각을 하지 못해서, 쉽게 구현할 수 있는 dfs를 이용하여 구현하였습니다.
  • 생각해야 하는 조건은 두가지가 있습니다.
    1. 사이클을 생성하는 경로
    2. 자체적으로 사이클이 생성되지 않지만, 다른 사이클이 생성된 곳으로 이동하는 경로
  • 해당 두가지를 모두 고려하여 설계를 해야 합니다.
  • 그러기 위해서 방문하지 않은 좌표를 dfs탐색하면서 방문표시된 곳에 맞닿을 경우, 사이클이 생성된 곳인지 체크하도록 하였습니다.
  • 만약 사이클이 생성된 곳에 도달했을 경우, SAFE ZONE을 더 만들지 않아도 됩니다.
  • 두가지 조건의 경로 모두, 사이클 처리를 해야하므로 dfs를 한번 더 이용하였습니다.(생각해보니 굳이 한번 더 하지 않아도 됐습니다. 사이클 번호가 중요한게 아니고 새로 생성된 사이클인지의 여부만 판단하면 되었기 때문입니다)

구현(20)

코드1
#include <iostream>
#define MAXN 1000
using namespace std;

int map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int cycle[MAXN][MAXN];
int ans;
int N,M;
int idx ;
int cycle_idx;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
void dfs(int x, int y){
    if (visited[x][y]) {
        if (cycle[x][y]==0) cycle_idx = idx;
        else cycle_idx = cycle[x][y];
        return;
    }
    visited[x][y] = true;
    int nx = x + dx[map[x][y]];
    int ny = y + dy[map[x][y]];
    dfs(nx,ny);
}
void dfs1(int x, int y, int num){
    if (cycle[x][y]) return;
    cycle[x][y] = num;
    int nx = x + dx[map[x][y]];
    int ny = y + dy[map[x][y]];
    dfs1(nx,ny,num);
}
int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0 ;i < N ; i++){
        for (int j = 0;j < M; j++){
            char tmp;
            scanf(" %1c",&tmp);
            int &ret = map[i][j];
            if (tmp == 'R') {
                ret = 0;
            }
            else if (tmp == 'D'){
                ret = 1;
            }
            else if (tmp == 'L'){
                ret = 2;
            }
            else ret = 3;
        }
    }
    for (int i = 0; i < N; i ++){
        for (int j= 0;j <M; j++){
            if (!visited[i][j]){
                idx++;
                dfs(i,j);
                // 새로운 사이클을 생성하는 경우
                if (cycle_idx == idx) {
                    ans++;
                }
                // 원래 있던 사이클에 들어가는 경로의 경우
                else idx--;
                dfs1(i,j,cycle_idx);
            }
        }
    }
    cout << ans <<"\n";
    return 0;
}
코드2 (최적화)
  • 코드1에서 dfs를 두번 사용하였는데, 이럴 필요가 없어서 한번만 사용해도 사이클을 찾을 수 있도록 변경하였습니다.
#include <iostream>
#define MAXN 1000
using namespace std;

int map[MAXN][MAXN];
int cycle[MAXN][MAXN];
int ans;
int N,M;
int idx ;
int cycle_idx;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
void dfs(int x, int y){
    if (cycle[x][y]) {
        cycle_idx= cycle[x][y];
        return;
    }
    cycle[x][y] = idx;
    int nx = x + dx[map[x][y]];
    int ny = y + dy[map[x][y]];
    dfs(nx,ny);
}

int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0 ;i < N ; i++){
        for (int j = 0;j < M; j++){
            char tmp;
            scanf(" %1c",&tmp);
            int &ret = map[i][j];
            if (tmp == 'R') {
                ret = 0;
            }
            else if (tmp == 'D'){
                ret = 1;
            }
            else if (tmp == 'L'){
                ret = 2;
            }
            else ret = 3;
        }
    }
    for (int i = 0; i < N; i ++){
        for (int j= 0;j <M; j++){
            if (!cycle[i][j]){
                idx++;
                dfs(i,j);
                if (cycle_idx == idx) ans++;
            }
        }
    }
    cout << ans <<"\n";
    return 0;
}
코드3 (union-find)
  • 처음에 생각했던 union-find알고리즘을 응용한 코드로, 공개코드처리된 functionx님의 코드를 참조하였습니다.
  • 아주 스마트하게도 x,y좌표를 인덱스로 변경하여 사이클 여부를 찾게 구현하셨습니다.
#include <iostream>
#include <cstring>
#define MAXN 1000
using namespace std;

int map[MAXN][MAXN];
int parent[MAXN*MAXN+1];
int ans;
int N,M;
int idx ;
int cycle_idx;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int find(int x){
    return parent[x] < 0 ? x: parent[x] = find(parent[x]);
}

int main(){
    scanf("%d%d",&N,&M);
    memset(parent,-1,sizeof(parent));
    ans = N*M;
    for (int i = 0 ;i < N ; i++){
        for (int j = 0;j < M; j++){
            char tmp;
            scanf(" %1c",&tmp);
            int &ret = map[i][j];
            if (tmp == 'R') {
                ret = 0;
            }
            else if (tmp == 'D'){
                ret = 1;
            }
            else if (tmp == 'L'){
                ret = 2;
            }
            else ret = 3;
        }
    }
    for (int i = 0; i < N; i ++){
        for (int j= 0;j <M; j++){
            int a = i*M+j;
            int b = (i+dx[map[i][j]])*M+(j+dy[map[i][j]]);
            a = find(a);
            b = find(b);
            if (a!=b) parent[a] = b,ans--;
        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 80ms

마무리

  • 이차원배열에서 사이클을 찾는 그래프 응용 문제였습니다. 2차원 그래프를 다루는데 익숙치 않아 union-find기법을 응용하지 못하였습니다.
 BOJ

Related Posts