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


백준 1697번 BFS 문제입니다. (문제풀이 해달라는 질문이 아닙니다!!)


#include <bits/stdc++.h>

using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
 
  vector<bool> visited(100001, false);
  vector<int> num(100001, 0);
  queue<int> q;

  q.push(n);
  visited[n] = true;

  while(true){
    int x = q.front();
    q.pop();
   
    for (int i=0; i<3; i++){
      int c;
      if (i == 0){
        if (x - 1 >= 0) c = x - 1;
        else continue;
      }
      else if (i == 1){
        if (x + 1 <= 100000) c = x + 1;
        else continue;
      }
      else if (i == 2) {
        if (x * 2 >= 0 && x * 2 <= 100000) c = x * 2;
        else continue;
      }
     
      if (c == k){
        cout << num[x] + 1;
        return 0;
      }
      else if (!visited[c]){
        q.push(c);
        visited[c] = true;
        num[c] = num[x] + 1;
      }
    }
  }
}


위의 코드가 제가 짠 코드인데, 몇가지 예시들 다 넣어봤는데 모두 잘 나와서


제출하니까 틀렸다고 나오는거에요


그래서 한참을 삽질하다가 백준 질문 게시판에서 반례 하나 찾았는데 그게 뭐냐면


n = 100000, k = 100000 입니다.


n과 k가 같을 때는 0이 나와야 하는데 제 코드는 2가 나오더라구요.


  if (n == k){
    cout << 0;
    return 0;
  }


중간에 위 코드 넣어주고 제출하니까 바로 통과됐습니다.



여기서 고민은... 저는 저런 특수케이스?를 고려해야 한다는 생각이 눈꼽만큼도 안들었고


완벽한데 왜 안되지? 이생각만 계속 했어요.


몇시간 낭비하다가 저 반례 보고 머리가 띵 했습니다... "완전 내 예상 밖이다, 나는 재능이 없는게 아닐까?" 하구요 ㅠㅠ


만약에 이게 코딩테스트였으면 생각만해도 끔찍해요


앞으로 더 많은 문제들을 풀건데 계속 이럴까봐 너무 막막합니다... 조언 부탁드려요