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

해결법

• K번째 바꾼 숫자들을 queue에 넣음
• ⭐️방문(중복) 숫자는 set으로 관리
• ⭐️총 K번 Swap 회차만큼 Swap을 할텐데, 각 회차가 될 때 마다 방문배열을 초기화해줘야 합니다. 무슨 말이냐면 이전에 나왔던 숫자가 나중에 나와도 됩니다. (출처 https://batory.tistory.com/309)

#1

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

string N;
int M,K;
queue<string> q;

string swap_c(int i, int j){
  string ret = N;
  char c1 = ret[i];
  char c2 = ret[j];
  ret[i] = c2;
  ret[j] = c1;
  return ret;
}

string bfs(string s){
  q.push(s);
  for(int k=1; k<=K; k++){
    int qsize = q.size();
    if(!qsize) break;
    for(int qq = 0; qq<qsize; qq++)
    {
      string tmp = q.front();
      q.pop();
      set<string> visited;
      for(int i = 0; i<M-1; i++){
        for(int j = i+1; j<M; j++){
          if(i==0 && tmp[j]=='0') continue;
          string swapped = swap_c(i,j);
          if(!visited.count(swapped)){
            q.push(swapped);
            visited.insert(swapped);
          }
        }
      }
    }
  }
  string ans = "0";
  while(!q.empty()){
    ans = max(ans,q.front());
    q.pop();
  }
  if(ans[0]=='0') return "-1";
  else return ans;
}

int main(){
  cin>>N>>K;
  M = N.size();

  cout<<bfs(N);
  
}

swapped를 출력해서 확인해봤더니 tmp가 어떤 것이든 같은게 계속 queue에 들어갔다.
왜그럴까 생각해봤는데, swap_c 함수에서 실수해놓고 몰랐던것 ^.ㅜ 어쩐지 같은것만 넣더라

#2

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

string N;
int M,K;
queue<string> q;

string swap_c(string s,int i, int j){
  string ret = s;
  char c1 = ret[i];
  char c2 = ret[j];
  ret[i] = c2;
  ret[j] = c1;
  return ret;
}

string bfs(string s){
  q.push(s);
  for(int k=1; k<=K; k++){
    int qsize = q.size();
    if(!qsize) break;
    for(int qq = 0; qq<qsize; qq++)
    {
      string tmp = q.front();
      q.pop();
      set<string> visited;
      for(int i = 0; i<M-1; i++){
        for(int j = i+1; j<M; j++){
          if(i==0 && tmp[j]=='0') continue;
          string swapped = swap_c(tmp,i,j);
          if(!visited.count(swapped)){
            q.push(swapped);
            visited.insert(swapped);
          }
        }
      }
    }
  }
  string ans = "0";
  while(!q.empty()){
    ans = max(ans,q.front());
    q.pop();
  }
  if(ans[0]=='0') return "-1";
  else return ans;
}

int main(){
  cin>>N>>K;
  M = N.size();

  cout<<bfs(N);
  
}

메모리 초과………,,
╭┈┈┈┈╯   ╰┈┈┈╮

 ╰┳┳╯    ╰┳┳╯

  메 　    　　 과

  모   　    　　라
     ╰┈┈╯
  리 ╭━━━━━╮　니
      ┈┈┈┈
　　초     　　 요

#3

visited set 위치 바꿔주고 해결

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

string N;
int M,K;
queue<string> q;

string swap_c(string s,int i, int j){
  string ret = s;
  char c1 = ret[i];
  char c2 = ret[j];
  ret[i] = c2;
  ret[j] = c1;
  return ret;
}

string bfs(string s){
  q.push(s);
  for(int k=1; k<=K; k++){
    int qsize = q.size();
    if(!qsize) break;
    set<string> visited;
    for(int qq = 0; qq<qsize; qq++)
    {
      string tmp = q.front();
      q.pop();
      for(int i = 0; i<M-1; i++){
        for(int j = i+1; j<M; j++){
          if(i==0 && tmp[j]=='0') continue;
          string swapped = swap_c(tmp,i,j);
          if(!visited.count(swapped)){
            q.push(swapped);
            visited.insert(swapped);
          }
        }
      }
    }
  }
  string ans = "0";
  while(!q.empty()){
    ans = max(ans,q.front());
    q.pop();
  }
  if(ans[0]=='0') return "-1";
  else return ans;
}

int main(){
  cin>>N>>K;
  M = N.size();

  cout<<bfs(N);
  
}

제출결과