📚 알고리즘
[백준 1600] 말이 되고픈 원숭이_bfs(c++)
[문제] https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net [접근방법] 1. 원숭이가 인접한 4방향으로 움직이는것과 말의 움직임으로 한번 움직이는 것을 모두 한번의 동작으로 친다 w >> h; //가로, 세로 queue q; //원숭이가 이동할 수 있도록 하는 큐 Pos pos = {0,0,0};//원숭이의 처음 시작점은 0,0 이동횟수는 0 q.push(pos); int** map = new int* [w]; memset(m..
[백준 17069] 파이프 옮기기 2(C++)
[문제] https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [접근방법] 1. 처음에 완전탐색(BFS)으로 문제를 풀이하려고 했다... 2. 하지만 메모리 초과의 이유로 풀수 없는 문제라고한다.. 3. 다이나믹프로그래밍을 써서 마지막 n-1,n-1 지점에 저장되어 있는 dp값이 정답! 4. 점화식을 구해 top-down이나 bottom-up 으로 쓰는 방법과는 다르게 3차원 배열을 이용하여 전에 기억하고 있는 값을 계속 더..