Algorithm/bfs

[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..

백준 13549 숨바꼭질3 c++ // pq를 이용한 bfs 구현방법

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제 그냥 bfs : 메모리초과? 가 났다. bfs는 비용이 모두 동일할때만 사용 가능하다. 해결 : 비용이 적은것부터 탐색하도록 pq에 담는다. 2. 전체코드 #include using namespace std; int n, k; int vis[100000 + 4]; int main() { ios_base::sync_with_stdio(0); cin.t..

프로그래머스 거리두기확인하기 c++ // bfs, check함수 활용방법, 문자열을 배열처럼 활용하는방법

https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문자열을 배열처럼 활용하는방법 auto place : places 후 place[i][j]로 접근하면 된다. places -> [POOOX, PPPPP..], [PPAP, ...] [...] place -> [POOOX, PPPPP, ...] place[i] - > POOOX place[i][0]=='P' 2. check함수 활용방법 1. check로 의사코드짜고 2. 이후에 구체적으로 구현..

프로그래머스 가장 먼 노드 c++ // bfs, 이동거리체크는 bfs

https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 1.1. 인접벡터에 집어넣기 1.2. bfs 1.3. 최대거리 계산 1.4. for문 : 최대거리에 있는 노드들 카운팅 2. 전체코드 #include using namespace std; queue q; int visited[20004]; vector adj[20004]; int max_distance; int solution(int n, vector edge) { int answe..