본문 바로가기

dfs

BOJ)1405 미친 로봇 문제: icpc.me/1405 각 방향으로 이동할 확률과 이동 횟수가 주어질 때 경로가 단순할 확률을 구하는 문제이다. dfs를 통한 4방향 탐색으로 각 방향으로 이동할 확률을 곱해서 brute force 해주면 된다. 1234567891011121314151617181920212223242526272829#include #include using namespace std;int n, visited[30][30];double p[4];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };double dfs(int x, int y, int cnt) { if (cnt == 0)return 1.0; double ret = 0.0; visited[x][y] = true; for .. 더보기
BOJ)5913 준규와 사과 문제: icpc.me/5913 (1,1)에서 (5,5)까지 모든 정점을 한번씩 다 들린 뒤 갈 수 있는 경로의 수를 구하는 문제이다. dfs를 이용하여 나올 수 있는 모든 경우를 탐색해주면 된다. 주의할점은 한번의 경로의 탐색이 끝난 뒤 visited를 해제해주어 다음 경로 탐색 때 그 정점을 방문할 수 있게 해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;int a[6][6], visited[6][6], k, x, y, r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { retu.. 더보기
BOJ)3109 빵집 문제: icpc.me/3109 맨 왼쪽부터 맨 오른쪽 까지 중복되지 않는 최대 경로의 개수를 구하는 문제이다. 우리는 x->y로 가는 경로가 있을 경우 무조건 오른쪽으로만 이동가능하므로 h라는 지점에서 갈 수 있는 길이없다면 다시 h를 밟아도 경로가 없다는걸 그리디하게 생각하면 알 수 있다. 이 생각에 기반하여 dfs를 이용하여 갈 수 있는 경우가 나오면 다른 방향을 탐색하지 않는 것으로 경로의 중복을 막아 답을 구해줄 수 있다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;int r, c, visited[10002][502], res;char a[10002][502];int dx.. 더보기
BOJ)14500 테트로미노 문제:icpc.me/14500 주어진 문제의 답은 모든 경우에 테트로미노를 다 대봄으로서 구할 수 있다. 주어지는 테트로미노의 5가지 모양중 ㅜ 모양을 제외한 4가지 모양은 DFS를 통하여 탐색이 가능하고 ㅜ모양만 따로 처리를 해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include using namespace std;int n, m, a[501][501], v[501][501], r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { r.. 더보기
BOJ)14502 연구소 문제: icpc.me/14502 N,M의 범위가 매우 적기 때문에 나올 수 있는 경우를 전부 확인해줄 수 있다. 6중 포문을 통하여 모든 경우에 벽을 세워본 후 dfs를 통하여 바이러스가 얼마나 퍼질 수 있는지 조사하여 그 최솟값을 전체 크기에서 벽을 제외한 값에서 빼주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std;int n, m, a[9][9], r, visited[9][9], b;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,.. 더보기
BOJ)2820 자동차 공장 문제: icpc.me/2820 문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다. 그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다. 이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다, 구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다. 1234567891011121.. 더보기
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 더보기
디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 더보기
이분 매칭(Bipartite Matching) 네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다. 이분 그래프는 다음과 같은 모양을 띄고 있습니다. 위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다. 이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다. 간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고 우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지.. 더보기
단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시다. 여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다. 이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요? 우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다. 아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다. 우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단.. 더보기