백준 16397 : 탈출

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

이번에 우리학교 코딩대회에 나갔다.. 복수전공 시작하고 아직 학교 수업은 자료구조를 듣는 터라

알고리즘에 관한 지식은 구글링하며 독학하며 주워들은 것 밖에 없다. ABC 세문제 밖에 못풀었는데

D와 K 2문제는 풀 수 있었을 것 같은데 아쉽게 계속 시간초과가 났다. (이 두 문제만 풀었어도..)

어쨌든 반성하는 의미에서 시험장에서는 못풀었지만 더 공부하며 나머지 문제를 다 풀어보려한다.

D번 문제였던 탈출은 시험장에서 계속 DFS밖에 생각이 안났다. 그것도 평소 DFS를 재귀로만 구현해서

문제를 풀어봤던지라 스택으로 짜는 것은 아무생각이 안들었음.

이 문제를 시험 다다음날 구글에 검색해보았는데 BFS로 풀었다고 한 순간 머리가 띵해졌다.

생각해보니 충분히 가능하겠다 싶었고 15분만에 바로 '성공' 뜨더라..

BFS도 시험장에서 언뜻 떠올랐긴 했는데 평소 BFS는 2차원행렬에서 최소거리 찾을 때 사용을 해보아서

이 문제가 일차원배열에서 BFS를 적용해볼 생각을 못했다. 하나 배운듯. 아무튼 이 문제도 최소를 찾는 것이고

visited 배열에 숫자를 1씩 늘려가는 방법으로 카운트하면 된다.

한편으로는 어이가 없고 한편으로는 또 한가지 배운것 같아서 기분은 좋다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

#include <iostream> #include <queue> #include <string> #define MAXSIZE 100000 using namespace std; int current, maxCount, target; int visited[MAXSIZE]; queue<int> q; string ret = "ANG"; void pressA(int n){ if(n + 1 > MAXSIZE-1 || visited[n + 1] != -1){ return; } q.push(n+1); visited[n+1] = visited[n] + 1; } void pressB(int n){ if(n * 2 > MAXSIZE-1){ return; } int tpn = n*2; string str = to_string(tpn); int ch = str[0] - '0'; ch--; str[0] = ch + '0'; int re = atoi(str.c_str()); if(visited[re] != -1){ return; } q.push(re); visited[re] = visited[n] + 1; } int main(){ fill(visited, visited+MAXSIZE, -1); cin >> current >> maxCount >> target; q.push(current); visited[current] = 0; while(!q.empty()){ int tp = q.front(); q.pop(); if(visited[tp] > maxCount){ break; } if(tp == target){ //find ret = to_string(visited[tp]); break; } pressA(tp); pressB(tp); } cout << ret << endl; return 0; }