Algorithm/bfs

[틀림] 백준 14867 물통 // map bfs

https://www.acmicpc.net/problem/14867*시도1dfs로 6가지 경우의수 탐색 -> 계속 fill A 만 호출되다 스택 오버플로우* 풀이가중치가 같은 최단거리는 ? bfs! 처음 찾은게 최단거리 보장but, 상태 : [a의 물][b의물] = [10만][10만] -> 메모리 초과상태관찰 -> 상태가 띄엄띄엄 있음 -> 즉, vis를 전부사용하지 않아도됨 -> map을 vis로 활용#includeusing namespace std; typedef long long ll;int a,b,c,d,ret=-1;map,int> vis;struct A { int q,w,cnt;};int main() { ios_base::sync_with_stdio(0); cin.tie(0); ..

[맞음] 백준 1600 말이 되고픈 원숭이 // 3차원 bfs

https://www.acmicpc.net/problem/1600* 풀이bfs 상태 : y,x,이동가능횟수,거리vis[y][x][이동가능횟수] : 방문했는지원숭이가 갈수있는곳을 dy,dx배열로 만들어놓기m이 y의 길이임에 주의 (m*n 행렬임)#includeusing namespace std; typedef long long ll;int n,m,k,ret=-1;int vis[204][204][34], arr[204][204];int dy[]={0,1,-1,0};int dx[]={1,0,0,-1};int dy2[]={-2,-2,-1,-1,1,1,2,2};int dx2[]={-1,1,-2,2,-2,2,-1,1};struct A { int y,x,cnt,dist; };int main() { ios_ba..

[틀림] 프로그래머스 보물지도 // 3차원 bfs

https://school.programmers.co.kr/learn/courses/15009/lessons/121690?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이최단거리는 bfs상태 : { y, x, 점프사용여부, dist }단순한 bfs는 vis를 방문여부용도 && 거리용도로 사용, but 복잡한경우 dist라는 상태를 따로 분리하는게 좋겠다.이문제는 앞쪽에서 방문여부체크, 종료조건을 체크하는 bfs가 유리.bfs는 먼저 도착한게 최단거리다.3차원 bfs 이해하기세계를 2개로 나눠서 그려보자.세계간 이동가능 여부를 그려보자.공통) +-1로 이동가능안쓴경우 ) +-2..

[Algo] 백준 벽부수고 이동하기 c++ // 최단거리는 bfs 3차원

* 2차원이 안되는 이유처음설계 상태 : (y, x , 그때 벽부순 count)를 두고 bfs를 돌리기if(next_cnt >= 2) continue; #include using namespace std;typedef long long ll;struct A { int y; int x; int cnt; // 여기좌표에 올때까지 부신 벽의갯수 A(int y, int x, int cnt) : y(y), x(x), cnt(cnt) {};};int n, m, arr[1004][1004], vis[1004][1004];int dy[] = { 1,0,-1,0 };int dx[] = { 0,1,0,-1 };ll ret; //배정된 예산중 최대값queue q;int main(){ cin..

[알고리즘] 리트코드 116. 각 노드의 다음 오른쪽 포인터 채우기 c++ // bfs 트리순회

* 의사코드핵심은 rightNode에 직전우측노드를 캐시해놓고next를 캐시된 그걸로 대입해주는것이다.레벨별로 (rightNode의 초기값은 nullptr 이다.)  * 전체코드class Solution {public: Node* connect(Node* root) { if(!root) return nullptr; //null check 후에 root->next 등에 접근가능함 queue q; q.push(root); while(q.size()){ Node* rightNode = nullptr; for(int i=q.size();i;i--){ //레벨별 구분위한 반복문(1,2,4...) ..

백준 16928 뱀과 사다리 게임 c++ // dp불가능한경우, bfs복습

https://www.acmicpc.net/problem/169281. dp불가능한경우1. dp는 단방향이고 사이클이 없는 그래프에서만 사용가능하다! 이문제의경우 뱀을만나는경우 뒤로돌아가기때문에 양방향이다!! ->  dp 불가 2. dp 주의점그럼에도 불구하고 dp로 짤때 실수를 많이 했는데,시행착오를 고쳐보자1. 의사코드(그래프)dp는 끝에도달(100)하면 그때 중 최소값을 골라(v표시)가는 알고리즘이다.이때, 98에서 dp=dfs이렇게 저장을 해줘야 "1"값이 저장되어 12로 그대로 전달된다.기존 : dfs만 돌려줬더니 dp초기값인 0이 12번노드로 리턴됬다....  3. 전체코드 dp(오답)오답인이유 : dp는 해당상태를 재탐색하지 않는 알고리즘인데,뱀을타고 역방향으로 이동하는경우 재탐색하면 더 나..

백준 9205 맥주마시면서걸어가기 c++ // bfs, 출력시 "\n을 빼먹지마라.."

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 1. 의사코드 sy,sx,ey,ex : 시작점, 끝점 좌표저장 vector : 편의점의 좌표들 저장 vis[i] : i번 편의점의 방문여부 저장 = > 중복방문 안하도록 50*20==1000이므로 1000미터 이내를 인접노드로 본다! if(거리 인접노드에 추가한다 2.bfs 복습(문어박사) 1. q초기값넣기, 초기화 등 2. cur값체크, !종료조건! 3.nxt값체크, 큐에넣기 3. 전체코드..

백준 5014 스타트링크 c++ // bfs 를 사용하라. (dfs는 시간초과)

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1.시행착오 범위가 1~f~1000000이므로 if(f>=0) continue; //정답 , 범위를 정확히 맞춰야함, 안맞추면 f==0일때를 탐색하여 오답이됨 if(f>0) continue; //오답! 2. 전체코드 #include using namespace std; int f, s, g, u, d,ret=987654321; int v[1000000 + 4]; int main() { cin.tie(0); c..