[백준] 2206번 벽 부수고 이동하기 (C++)

문제 주소 백준 2206번 벽 부수고 이동하기 알고리즘 BFS 힌트 어떤 위치에 온 상태가 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지 구분 해야 한다. 풀이 위치(a, b)와 상태(w : 벽을 부쉈다면 1 부수지 않았다면 0)를 원소로 가지는 dot구조체를 만들어 준다. check배열도 위치와 상태를 담을 수 있도록 3차원으로 선언 해 준다. 현재의 위치가 목표 위치라면 ans를 출력하고 main 함수를 종료 해 준다.q를 다 확인 할 때까지 목표점에 도착하지 못하였다면 목표점에 도달할 수 없는 것이므로 -1을 출력해준다. 벽이 있고 벽을 뚫지 않았다면 q에 넣어주고 벽이 없다면 check배열을 하여 중복되지 않도록 q에 넣어준다. #include #include using namespace ..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 21.
• textsms

[백준] 2485번 키 순서 (C)

출처 한국정보올림피아드 지역본선 2011 초등부 4번 문제 번호 백준 2458번 키 순서 코드업 4714 : 키 순서 알고리즘 DFS 힌트 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음 나보다 큰 아이보다 큰 아이는 나보다 큼 나보다 작은 아이보다 작은 아이는 나보다 작음 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음 풀이 들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 20.
• textsms

[백준] 2606번 바이러스 (C)

출처 2004 전국 본선 초등3 힌트 단순 탐색 풀이 양방향 그래프를 만들어 준 뒤, 연결 되어 있는 컴퓨터들을 찾아가면 됩니다. 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 #include using namespace std; int com[101][101]; int check[101]; int ans=-1; int v,e; void dfs(int n){ check[n]=1; ans++; for(int i=1;i>v>>e; for(int i=0;i>a>>b; com[a][b]=1; com[b][a]=1; } int n; dfs(1); cout

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 10.
• textsms

[코드업] 3212 : 위상 정렬(topological sort) (C)

알고리즘 위상정렬 풀이 위상정렬을 하 되, 우선순위가 같은 경우 작은 숫자부터 출력해야 하기 때문에 한번의 시행이 끝날 때 마다 다음 시행할 '한 개'의 숫자를 Queue에 넣어준다. ( 이런 우선순위 조건이 없을 경우엔 간선이 지워지는 노드들만 확인 하면 된다. ) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#include#include#includeusing namespace std; queue q;queue ans;vector vec[201]; int ind[201]; int main(){ int v,n; cin>..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 9.
• textsms