코딩코딩

www.acmicpc.net/problem/1520

DFS + DP 사용

처음 접근은 BFS를 사용했지만 시간 초과가 나왔다. 상하좌우 4면을 다 체크하면서 500x500의 배열을 탐색하는 경우

최악의 경우에 4^(500*500) 인걸,,,생각 못했다,,,,,

dp로 어떻게 접근해야하는지 감이 안잡혀서 구글링을 해봤는데, dp[a][b] = c 라고 한다면, (a,b) ~(n-1,m-1)에 c가지의 경로로 도달가능 이 식을 보고,,, 다시 재 도전했다. 

이미 탐색을 한 위치라면, 굳이 또 돌지않고 예전에 구한 값을 재활용 하며 시간을 줄여주기,,,,,난 아직 멀었구나,,,,

#include <bits/stdc++.h>

using namespace std;

int n,m;
int board[501][501];
int dp[501][501];
int dx[4] ={0,1,0,-1};
int dy[4] ={1,0,-1,0};

int dfs(int x, int y){
  if(x == n-1 &&  y == m-1) return 1;
  if(dp[x][y] != -1) return dp[x][y];

  dp[x][y] = 0;
  for(int i=0; i<4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
    if(board[nx][ny]>= board[x][y]) continue;
    dp[x][y] += dfs(nx,ny);
  }

  return dp[x][y];
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>board[i][j];
    }
  }
  memset(dp,-1,sizeof(dp));
  cout<<dfs(0,0)<<"\n";
  
}

www.acmicpc.net/problem/5014

BFS 사용 

숨바꼭질 문제와 유사하게 접근했다.

시작 위치와 , 버튼을 누르는 횟수를 아예 pair로 함께 저장했다. 

그리고 조건에 맞게 U / D에 따라 범위를 초과하지 않고, 방문하지 않았다면 que에 넣어주고 버튼 횟수+1을 진행했다.

최근에 숨바꼭질 시리즈를 풀어서 그런지 문제 접근과 진행은 수월했는데, 계속 제출해도 56퍼정도에 틀렸습니다가 나와서  한 15분정도 삽질을 했다. 알고보니,,, 현위치 -D를 했을 때의 범위를  > 0 인데,    0<= U,D <=1000000 조건만 보고  >=0으로 해둬서 계속 틀린거였다,,,, 범위만 수정해주니 문제 없이 해결,, 

 (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

진짜 허무하네 ㅇ<-< ,, 문제 조건을 잘 보자,,,,제발,,~~

#include <bits/stdc++.h>

using namespace std;

int f,s,g,u,d;
bool visited[1000001];

int bfs(){

  queue<pair<int,int>> que;
  que.push({s,0});

  visited[s] = 1;

  while(!que.empty()){
    auto cur = que.front();
    que.pop();

    if(cur.first == g) {
      return cur.second;
    }

    if(cur.first+u <=f && !visited[cur.first+u]){
      que.push({cur.first+u, cur.second+1});
      visited[cur.first+u] = 1;
    }

    if(cur.first-d >0 && !visited[cur.first-d]){
      que.push({cur.first-d, cur.second+1});
      visited[cur.first-d] = 1;
    }
  }
  return -1;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>f>>s>>g>>u>>d;
  int ans = bfs();
  if(ans>=0){
    cout<<ans<<"\n";
  }
  else{
    cout<<"use the stairs"<<"\n";
  }
}

www.acmicpc.net/problem/2589

BFS

다른 문제와 달리 시작-끝 좌표가 없기 때문에 모든 L의 위치마다 다 BFS 탐색을 진행해야한다.

그리고 그 중 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지들의 값을 출력하면 된다.

주어진 보물섬 지도의 모든 L을 시작점으로 다 탐색해야 하기 때문에, 이동하며 걸리는 시간을 기록할 visited 배열을 함수 내에 넣어 매번 -1로 초기화 해준다. ... 거리 -1하기 싫어서 그냥 -1로 초기화 진행했다. 

bfs를 돌며 최단 거리로 이동했을 때의 가장 긴 시간을 리턴값으로 주며   각 L에서의 BFS 탐색시 가장 오래 걸렸던 시간을 최종으로 출력해준다.

시험기간인데 백준푸는 나,, 정상인가요 ㅁㅇㄹ

#include <bits/stdc++.h>

using namespace std;

string board[51];
int visited[51][51];
int n,m;
int dx[4] = {0,1,0,-1};
int dy[4] ={1,0,-1,0};

int bfs(int a, int b){
  memset(visited,-1,sizeof(visited));

  queue<pair<int,int>> que;

  que.push({a,b});
  visited[a][b] = 0;
  int dist = 0;
  while(!que.empty()){
    auto cur = que.front();
    que.pop();

    for(int i=0; i<4; i++){
      int nx = cur.first + dx[i];
      int ny = cur.second + dy[i];
      dist = max(dist,visited[cur.first][cur.second]);
      if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
      if(visited[nx][ny] >=0 || board[nx][ny] == 'W') continue;
      que.push({nx,ny});
      visited[nx][ny] = visited[cur.first][cur.second] + 1;
      
    }
  }
  return dist;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<n; i++){
    cin>>board[i];
  }
  int cnt =0;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(board[i][j] == 'L'){
         cnt = max(cnt,bfs(i,j));
       }
    }
  }
  cout<<cnt<<"\n";
  
}

www.acmicpc.net/problem/3055

BFS 사용 

1. 물을 기준으로 BFS 탐색

- 이미 방문 했거나, 돌을 만나거나, 비버의 굴을 만나는 경우를 제외하고 물을 채운다.

2. 고슴도치를 기준으로 BFS 탐색

- 이미 방문했거나, 벽을 만나거나, 다음으로 이동할 곳이 이미 물이 지났고, 그 장소로 이동했을 때의 시간에 이미 물이 차있는 경우는 제외하며 남은 곳을 이동을 한다. 

- 탐색을 하며 비버의 굴 D를 마주한 경우에 이동횟수를 출력해준다. 

- 탈출하지 못하는 경우 KAKTUS 출력 

예전에 풀었던 4179 불! 이라는 문제와 아주 유사하다.

포인트는 물/고슴도치  2가지 각 따로 탐색을 진행해야 하며, 주어진 조건에 따라 

고슴도치가 비버의 굴을 만난경우 탈출 할 수 있으며, 이미 물이 채워진 경우에는 지나지 못하도록 조건을 잡아주면 된다.

#include <bits/stdc++.h>

using namespace std;

string board[51];
int dist1[51][51];
int dist2[51][51];
int dx[4] ={0,1,0,-1};
int dy[4] = {1,0,-1,0};
int n,m;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cin>>n>>m;

  for(int i=0; i<n; i++){
    cin>>board[i];
  }

  memset(dist1,-1,sizeof(dist1));
  memset(dist2,-1,sizeof(dist2));

  queue<pair<int,int>> que1;
  queue<pair<int,int>> que2;

  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(board[i][j]=='*'){
        que1.push({i,j});
        dist1[i][j] = 0;
      }

      if(board[i][j]== 'S'){
        que2.push({i,j});
        dist2[i][j] = 0;
      }
    }
  }

  while(!que1.empty()){
    auto cur = que1.front();
    que1.pop();

    for(int i=0; i<4; i++){
      int nx = cur.first + dx[i];
      int ny = cur.second + dy[i];

      if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
      if(dist1[nx][ny] >=0 || board[nx][ny] == 'X'  || board[nx][ny]=='D') continue;
      que1.push({nx,ny});
      dist1[nx][ny] = dist1[cur.first][cur.second] +1;
    }
  }

  while(!que2.empty()){
    auto cur = que2.front();
    que2.pop();

    for(int i=0; i<4; i++){
      int nx = cur.first + dx[i];
      int ny = cur.second  + dy[i];
      
      if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
      
      if(board[nx][ny] == 'D'){ //고슴도치 탈출 조건 
        cout<<dist2[cur.first][cur.second]+1<<"\n";
        return 0;
      }

      if(dist2[nx][ny]>=0 || board[nx][ny] == 'X') continue;
      if(dist1[nx][ny] !=-1 && dist1[nx][ny]<=dist2[cur.first][cur.second]+1) continue;
      dist2[nx][ny] = dist2[cur.first][cur.second] +1;
      que2.push({nx,ny});
    }
  }
  cout<<"KAKTUS"<<"\n";

}

www.acmicpc.net/problem/13549

처음에는 당연히 순간 이동할 때만 시간 초 변화없이 그대로 BFS 쓰면 된다는 생각에 너무 쉽다 ~ 하고 바로 틀렸다

가장 빠른 시간을 구해야하기 때문에, 0초가 걸리는 순간이동을 위해 우선순위 큐로 구현을 했지만,,,계속 틀렸습니다가 나와서 방법을 찾아보니 deque를 이용하는 경우가 있어서 사용했다. 

순간이동을 우선으로 사용하는 방법이 가장 빠른 시간을 구할 수 있기 때문에, 순간이동 하는 경우에만 deque에 앞에 넣어주고, 그 외의 방법은 뒤로 넣어주며 탐색하는 방식으로 구현했다.  피곤하네,, 

#include <bits/stdc++.h>

using namespace std;

int n,k;
bool visited[100001];

int bfs(){
  deque<pair<int,int>> dq;

  dq.push_front({n,0});
  visited[n] = 1;

  while(!dq.empty()){
    auto cur = dq.front();
    dq.pop_front();

    if(cur.first == k){
      return cur.second;
    }

    if(cur.first*2 <=100000 && !visited[cur.first*2]){
      dq.push_front({cur.first*2 , cur.second});
      visited[cur.first*2] = 1;
    }
    if(cur.first+1 <=100000 && !visited[cur.first+1]){
      dq.push_back({cur.first+1, cur.second+1});
      visited[cur.first+1] = 1;
    }
    if(cur.first-1 >=0 && !visited[cur.first-1]){
      dq.push_back({cur.first-1, cur.second+1});
      visited[cur.first-1] = 1;
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>k;
  cout<<bfs()<<"\n"; 
}

www.acmicpc.net/problem/11723

한 달전에 풀었을 때는 계속 틀렸습니다가 나와서 안풀고 있다가 재도전 !

주어진 조건을 하나씩 구현하면 된다. 벡터를 사용하여 구현하였다.

백터내에 찾는 값이 존재하는지는 C++의 find 함수 사용 , 요소의 인덱스 위치는 find_if 함수도 있지만 , 그냥 따로 for문을 돌며 찾는 값이 있는 인덱스 위치를 리턴하는 함수를 구현했다. 

#include <bits/stdc++.h>

using namespace std;
int n;
vector<int> vec;

int checkOut(int num){
  for(int i=0; i<vec.size(); i++){
    if(num == vec[i]){
      return i;
    }
  }
  return -1;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  while(n--){
    string s;
    int num;
    cin>>s;
    if(s=="add"){
      cin>>num;
      auto it = find(vec.begin(),vec.end(),num);
      if(it ==vec.end()){
        vec.push_back(num);
      }
    }
    else if(s=="remove"){
      cin>>num;
      auto it = find(vec.begin(),vec.end(),num);
      if(it != vec.end()){
        int  i = checkOut(num);              
        vec.erase(vec.begin()+i);
        
      }
    }
    else if(s =="check"){
      cin>>num;
      auto it = find(vec.begin(),vec.end(),num);
      if(it != vec.end()){
        cout<<1<<"\n";
      }else{
        cout<<0<<"\n";
      }
    }
    else if(s=="toggle"){
      cin>>num;
      auto it = find(vec.begin(),vec.end(),num);
      if(it != vec.end()){
        int i = checkOut(num);       
        vec.erase(vec.begin()+i);        
      }else{
        vec.push_back(num);
      }
    }
    else if(s=="all"){
      vec.clear();
      for(int i=1; i<=20; i++){
        vec.push_back(i);
      }
    }
    else if(s =="empty"){
      vec.clear();
    }
  }
}

www.acmicpc.net/problem/16171

문자열 관련 문제 

입력받은 문자열의 크기 만큼 돌며, 숫자를 제외한 문자를 temp에 저장해준다. 

그리고 string의 find함수를 사용하여 찾고자 하는 키워드가 temp에 존재하는지 확인

여기서 중요한 점은 find함수는 리턴 값을 찾는 문자의 인덱스 위치를 알려준다. 만약 찾는 문자가 문자열에 없는 경우

엄청 큰 값을 반환하기 때문에 단순히 temp.find(s) >=0 으로 조건을 두면 안된다.   

temp.find(s)==string::npos

이와 같이 찾고자하는 문자열을 못찾았을 때, string ::npos 라는 조건으로 두어야 한다 !!! 이게 포인트

이부분만 잘 체크했다면 쉽게 풀 수 있는 문제다.

#include <bits/stdc++.h>

using namespace std;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  string str;
  cin>>str;
  string s;
  cin>>s;
  string temp = "";
  for(int i=0; i<str.size(); i++){
    if(str[i]>='0' && str[i]<='9') continue;
    else{
      temp+=str[i];
    }
  }
  if(temp.find(s)==string::npos){
    cout<<0<<"\n";
  }else{
    cout<<1<<"\n";
  }
 
}

www.acmicpc.net/problem/1244

남학생 / 여학생 에 따라 조건에 맞게 구현하면 된다.

남학생 (=1)인 경우 입력된 값의 배수 위치의 값을 변경해준다.

여학생 (=2)인 경우 일단 입력된 값 위치의 값을 변경해주고, while문을 돌며 왼쪽, 오른 쪽의 요소가 대칭으로 같은 경우에 요소 값을 반전 시켜줌 

#include <bits/stdc++.h>

using namespace std;

int arr[101];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin>>n;

  for(int i=1; i<=n; i++){
    cin>>arr[i];
  }

  int t;
  cin>>t;
  while(t--){
    int a,b;
    cin>>a>>b;

    if(a==1){
      for(int i=b; i<=n; i+=b){
        arr[i] = !arr[i];
      }
    }
    else{
      int left = b-1;
      int right =b+1;
      arr[b] = !arr[b];

      while(left>=1 && right<=n){
        if(arr[left] != arr[right]){
          break;
        }
        arr[left] = !arr[left];
        arr[right] = !arr[right];
        left --;
        right ++;
      }

    }
  }

  for(int i=1; i<=n; i++){
    cout<<arr[i]<<" ";
    if(i%20 ==0) cout<<"\n";
  }
}

www.acmicpc.net/problem/14467

그래프 탐색 문제 풀기 싫어서 구현으로 도망 

배열 값을 -1로 초기화 해주고 n만큼 입력을 받으며 

처음 입력받는 경우엔 값을 넣어준다.

입력받은 적이 있고, 기존에 입력된 값과 다르다면 새로 갱신해주고, 이는 길을 건넌 것 이기 때문에

개수를 세어준다. 

코테가 다 이정도만 나오면 얼마나 좋을까,,,,,,,,,,,,,,,,,,,,,,,,

#include <bits/stdc++.h>

using namespace std;

int arr[101];
int n;


int main(void){
  ios::sync_with_stdio(0);
  cin>>n;
  memset(arr,-1,sizeof(arr));
  int cnt =0;

  for(int i=0; i<n; i++){
    int a,b;
    cin>>a>>b;
    if(arr[a]== -1){
      arr[a] = b;
    }else if( arr[a] != b){
      arr[a] = b;
      cnt++;
    }
  }
  cout<<cnt<<"\n";

}

www.acmicpc.net/problem/14940

'2' 가 있는 위치에서 부터의 탐색 거리를 적어주면 된다.  = BFS 사용

크게 어렵지 않았지만, 탐색하며 원래 땅인 부분에 접근하지 못한경우 -1을 출력하는 부분에서 자꾸 틀렸습니다가 나왔다.... 바로 2중 for문을 돌면서 방문하지 않고, 원래 땅인 =1 인 요소의 위치에 -1을 출력하려 했지만 왜 자꾸 오류가 나는지 ㄱ-  .. 사실 아직도 모르겠다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 그냥 따로 원래 땅이면서 접근 안한 위치의 배열 값을 -1로 바꿔주고 한번에 출력했더니  통과됐다.

1. 2차원 배열로 요소 값을 입력받으며 '2'가 입력된 위치를 que에 저장, 위치 값을 0으로 수정하고 방문 표시

2. que가 비어있을 때 까지 돌면서 board가 벽이 아니며 방문하지 않은 요소의 값을 이동 거리로 갱신해주며 방문표시

3. 방문할 수 있는 땅이지만, 방문 안한경우 -1로 바꿔줌

4. 배열 출력 

#include <bits/stdc++.h>

using namespace std;
int n,m;
int board[1001][1001];
bool visited[1001][1001];
int dx[4] ={0,1,0,-1};
int dy[4] ={1,0,-1,0};


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  queue<pair<int,int>> que;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>board[i][j];

      if(board[i][j] ==2){
        que.push({i,j});
        board[i][j] = 0;
        visited[i][j] =1;
      }
      
    }
  }

  while(!que.empty()){
    int x = que.front().first;
    int y = que.front().second;

    que.pop();

    for(int i=0; i<4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
      if(board[nx][ny]==0 || visited[nx][ny]) continue;

      que.push({nx,ny});
      visited[nx][ny] = 1;
      board[nx][ny]  = board[x][y] + 1;
    }
  }


  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(board[i][j]==1 && !visited[i][j]){
          board[i][j] = -1;
      }     
    }  
  }


  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cout<<board[i][j]<<" ";
    }
    cout<<"\n";
  }
}