본문 바로가기

backjoon3

[BFS] 2206 벽 부수고 이동하기 #include #include using namespace std; struct Pos { int x, y, b; }; queue q; char a[1001][1001]; int dist[1001][1001][2]; int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 9. 12.
[백준] 1694 숨바꼭질 BFS를 잘 활용하면 되는 문제. 그래프를 잘 생각 해보자. 각 숫자들을 그래프의 노드라고 했을 때, 1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고, x노드에서 2x노드로 가는 간선들이 있다. BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데, V = 100,000, E < 300,000 이면 충분할 거라고 생각했다. 참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다. 나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다. #include #include #include using namespace std; int d[100001]; int main() { int n.. 2019. 9. 12.
11729 하노이 탑 접근 장대 1, 2, 3이 있고, 1에 원판 3개가 있을 때, 이 원판을 모두 크기 순에 맞게 장대 3에 옮겨야 한다. 그 과정을 살펴보자. a b 는 a의 맨위의 원판을 b의 맨 위로 옮긴다는 뜻이다. 자 머리속으로 상상해보자. 그러면서 일반화 해보자.(n개의 원판으로!) 1 3 1 2 3 2 ---------- 1) 지금 이상황은 1에서 제일 큰 원판이, 2에 n-1개의 원판이 순서대로 있는 상황이다. 1 3 ---------- 2) 1에 있는 가장 큰 원판을 3으로 보낸다. 2 1 2 3 1 3 ---------- 3) 2에서 n-1개의 원판을 3으로 보내는 상황이다. 함수 f(a, b, n_disk)를 정의하고 맨처음 상황을 f(1, 3, 3)으로 생각해보자. 1)의 상황을 다시 한번 보자. f(.. 2019. 6. 28.
728x90

티스토리툴바