boj 16957: 체스판 위의 공

https://www.acmicpc.net/problem/16957

16957번: 체스판 위의 공

처음에 그냥 DAG 그래프 형식으로 만들고 dfs로 푸는 방식이었는데 시간초과가 뜬다. A->B->C에서 A가 B를 거치고 C에 도달하는 형식이면, B를 이미 거쳤으므로 어떤 좌표가 B에 해당되면, B도 C에 다다른다는 결과치를 배열에 저장하고, B에서 따로 탐색시작 안해도 되도록 만들어 놨는데 시간초과가 뜨는것이다. (이유는 왠지 모르겠다.)

#include<bits/stdc++.h>
using namespace std;

int r,c,arr[501][501],num[501][501],dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1},final_[501][501];
int format_to_num(int y, int x){
  return y*c+x;
}
pair<int,int> format_to_pos(int k){
  return {k/c,k%c};
}

bool inrange(int y, int x){
  return y>=0&&y<r&&x>=0&&x<c;
}

vector<int> v[250001];

int dfs(int here){
  for(auto& p: v[here]){
    return final_[format_to_pos(here).first][format_to_pos(here).second] = dfs(p);
  }
  return final_[format_to_pos(here).first][format_to_pos(here).second] = here;
}

int main(){

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  memset(final_,-1,sizeof(final_));

  cin>>r>>c;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin>>arr[i][j];
    }
  }
  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      bool can=false;
      int minimum = arr[y][x],posy,posx;
      for(int dir=0;dir<8;dir++){
        int ny=y+dy[dir], nx=x+dx[dir];
        if(inrange(ny,nx)){
          if(arr[ny][nx]<minimum){
            can=true;
            minimum=min(minimum,arr[ny][nx]);
            posy=ny,posx=nx;
          }
        }
      }
      if(can){
        v[format_to_num(y,x)].push_back(format_to_num(posy,posx));
      }
    }
  }
  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      if(final_[y][x]==-1){
        int ret=dfs(format_to_num(y,x));
        final_[y][x] = ret;
        num[format_to_pos(ret).first][format_to_pos(ret).second]++;
      }else{
        num[format_to_pos(final_[y][x]).first][format_to_pos(final_[y][x]).second]++;
      }
    }
  }
  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      cout<<num[y][x]<<" ";
    }
    cout<<'\n';
  }

  return 0;
}

그냥 그래서 UNION FIND 방식이 있어서, 특정 좌표에서 8방면만 탐색해서 젤 값 작은것만 p[here]=8방향젤작은 좌표

로 저장을 하고 각 좌표의 최종다다르는 값을 FIND로 찾는 방식으로 구현하였다.

 

#include<bits/stdc++.h>
using namespace std;

int r,c,arr[501][501],num[501][501],dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
int p[250001];
int format_to_num(int y, int x){
  return y*c+x;
}
pair<int,int> format_to_pos(int k){
  return {k/c,k%c};
}

bool inrange(int y, int x){
  return y>=0&&y<r&&x>=0&&x<c;
}


int Find(int x){
  if(x==p[x]) return x;
  return p[x] = Find(p[x]);
}

int main(){

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=0;i<250001;i++) p[i]=i;

  cin>>r>>c;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin>>arr[i][j];
    }
  }
  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      bool can=false;
      int minimum = arr[y][x],posy,posx;
      for(int dir=0;dir<8;dir++){
        int ny=y+dy[dir], nx=x+dx[dir];
        if(inrange(ny,nx)){
          if(arr[ny][nx]<minimum){
            can=true;
            minimum=min(minimum,arr[ny][nx]);
            posy=ny,posx=nx;
          }
        }
      }
      if(can){
        p[format_to_num(y,x)] = format_to_num(posy,posx);
      }
    }
  }

  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      auto k =format_to_pos(Find(format_to_num(y,x)));
      num[k.first][k.second]++;
    }
  }

  for(int y=0;y<r;y++){
    for(int x=0;x<c;x++){
      cout<<num[y][x]<<" ";
    }
    cout<<'\n';
  }


  return 0;
}