본문 바로가기

BFS

BOJ)1938 통나무 옮기기 문제: icpc.me/1938 BFS를 이용하여 답을 구해줄 수 있다. 구현이 상당히 귀찮다 ... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #include #include using namespace std;struct ele { int x, y, z; ele(int x, int y, int z) :x(x), y(y), z(z) {} ele() {}};int dx[] = { 1,-1,0,0,0 };int dy[].. 더보기
UVaOJ)12797 Letters 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4662 NxN의 맵이 주어질 때 1,1에서 n,n까지의 최단거리를 구하는 문제이다. 단 제약조건이 있는데 발판으로 주어지는 알파벳중에 대문자나 소문자 하나를 정해놓고 일관성있게 밟아야 한다. 알파벳이 최대 10개밖에 없기 때문에 상태에 대하여 비트마스킹을하여 넘겨주어 BFS를 1024번만 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #incl.. 더보기
UVaOJ)10968 KuPellaKeS 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909 도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다. 연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다. 우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자. 그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나.. 더보기
BOJ)13460 구슬탈출2 문제: icpc.me/13460 빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다. 우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include using namespace std;int n, m, disc[11][11][11][11], bx, by, rx, ry;char a[11][11];int .. 더보기
BOJ)1194 달이 차오른다, 가자. 문제: icpc.me/1194 가중치 없는 그래프에서의 최단거리를 구해야 하므로 BFS를 이용하면 된다, 이때 열쇠라는 조건이 추가로 붙는데 우리는 열쇠를 쥐고 있는 상태를 비트마스킹을 통하여 표현해주면 된다. qu의 3번째 인자는 해당 상태가 가지는 열쇠를 비트로 표현한 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include using namespace std;int n, m, disc[51][51][1 더보기
BOJ)2146 다리만들기 문제: icpc.me/2146 dfs를 이용하여 각 나라들을 구분해준 후 bfs를 이용하여 각 나라들에서 어떤 다른 나라로 갈 수 있는 최단 거리를 모두 구해준 뒤 그 중 최솟값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;int n, a[101][101], disc[101][101], c;bool chk(int x, int y) { return 0 더보기
BOJ)5427 불 문제: icpc.me/5427 가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다. 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include #include using namespace std;int t, w, h, sx, sy;char a[1001][1001];in.. 더보기
BOJ)2636 치즈 문제: icpc.me/2636 공기와 닿는 부분의 치즈가 하루마다 녹을 때 치즈가 다 녹는데 걸리는 시간과 전부 다 녹기 직전 치즈의 개수를 출력하는 문제이다. bfs를 이용하여 공기와 닿는 부분을 기록해준 뒤 날이 바뀔 때 치즈를 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #include using namespace std;int n, m, a[101][101], b[101][101], r, f;int dx[] = { 0.. 더보기
디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 더보기

티스토리툴바