티스토리 뷰
문제: icpc.me/5913
(1,1)에서 (5,5)까지 모든 정점을 한번씩 다 들린 뒤 갈 수 있는 경로의 수를 구하는 문제이다.
dfs를 이용하여 나올 수 있는 모든 경우를 탐색해주면 된다.
주의할점은 한번의 경로의 탐색이 끝난 뒤 visited를 해제해주어 다음 경로 탐색 때 그 정점을 방문할 수 있게 해주어야 한다.
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 | #include <cstdio> #include <algorithm> 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) { return 0 < x&&x < 6 && 0 < y&&y < 6; } void dfs(int x, int y, int z) { if (x==5&&y==5) { if (z == 25 - k) r++; return; } visited[x][y] = 1; for (int i = 0; i < 4; i++) { int cx = x + dx[i]; int cy = y + dy[i]; if (chk(cx, cy) && !visited[cx][cy] && !a[cx][cy]) dfs(cx, cy, z + 1); } visited[x][y] = 0; } int main() { scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%d%d", &x, &y); a[x][y] = 1; } dfs(1, 1, 1); printf("%d\n", r); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)3683 고양이와 개 (0) | 2017.04.27 |
---|---|
BOJ)2610 회의준비 (0) | 2017.04.24 |
BOJ)5913 준규와 사과 (0) | 2017.04.21 |
BOJ)3109 빵집 (0) | 2017.04.21 |
BOJ)1251 단어 나누기 (0) | 2017.04.20 |
BOJ)14503 로봇 청소기 (0) | 2017.04.17 |
- TAG
- dfs
댓글
공지사항
- Total
- 308,359
- Today
- 31
- Yesterday
- 189
TAG
- BFS
- 위상 정렬
- MST
- 힙
- SCC
- 네트워크 플로우
- partial sum
- dfs
- MCMF
- 에라토스테네스의 체
- 분할 정복
- 세그먼트 트리
- Suffix Array
- 트리
- 라인 스위핑
- disjoint-set
- lca
- brute force
- 그리디 알고리즘
- 다익스트라
- LCP array
- 좌표 압축
- 플로이드 워셜
- KMP
- 이분 탐색
- 이분 매칭
- 수학
- 디닉
- lazy propagation
- 다이나믹 프로그래밍