백준1927 (SILVER 1) - 숨바꼭질

1 minute read

Published:

[SILER 1] 숨바꼭질

틀린 풀이

좌표를 한칸씩 앞으로, 뒤로 혹은 2배 가능. -> 3가지 경우를 고려한 방식으로 DP로 풀었다. but 시간 초과.

이유는 DP 방식으로 터무니 없는 방식(예를 들어 1부터 10만까지 다 +1) 까지 고려하기에.

정답

정답으로 향하는 핵심은 ‘가장 빠른 시간’ = 최단 거리. => BFS 이용. 각 단계에 가능한 && 가장 빨리 해당 칸에 도달한 경우만 고려 = 복잡도가 준다.

//시간 초과...
//처음에 DP로 접근했으나 시간이...
//최단 거리 찾는 BFS 문제였다.

//BFS는 짧은 거리 케이스가 먼저 처리되서 빠를 것.
//DP는 깊이 우선 탐색 처럼 작동해, 말도 안되는 케이스까지 일단 다 계산후 갱신할테니 느릴 것.
#include<iostream>
#include<deque>
#include<tuple>

bool visit[100001];
int s, e;



int main() {
  for(int i = 0; i<=100000; i++){
    visit[i] = false;
  }

  std::cin >> s >> e;

  std::deque<std::tuple<int,int>> q;
  q.push_back(std::make_tuple(s,0));
  visit[s] = true;

  while(true){
    int posi, turn;
    std::tie(posi,turn) = q.front();
    visit[posi] = true;//이걸 안했네.. 처음에 visit 배열 추가할때 부터 이를 어떻게 관리할지 생각하고 처리해 줬어야지...
    q.pop_front();
    if(posi == e){
      std::cout << turn;
      return 0;
    }

    if(posi+1 >=0 && posi+1 <= 100000 && !visit[posi+1]){
      q.push_back(std::make_tuple(posi+1,turn+1));
    }
    if(posi-1 >=0 && posi-1 <= 100000 && !visit[posi-1]){
      q.push_back(std::make_tuple(posi-1,turn+1));
    }
    if(posi*2 >=0 && posi*2 <= 100000 && !visit[posi*2]){
      q.push_back(std::make_tuple(posi*2,turn+1));
    }
  }
}

단순 구현 실수

  • visit을 표시 안해줘서 계속 스택 오버 플로가 났었다. => BFS 고려할 것 (방문해서 visit 표시, 방문시 visit 하지 않았고, 문제만의 방문할 조건을 만족하는지, 유효한 인덱스인지.) 조심!

이외

  • DP 풀이도 된다곤한다. 담에 시간나면 한번 찾아봐도 괜찮을지도?