05-20 07:35
벤치마킹
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 싱가폴중학교수학문제
- 에어아시아
- 양양솔비치조식
- 가족소고기외식
- 종이캐리어
- 아이혼자다녀옴
- 고마워다음
- 사진문자추출
- 주차넉넉
- 커피쏟음
- DFS
- 검색완료
- 파이썬
- 오트눈썰매장
- 사진에서 글자추출
- 영통칠프로칠백식당
- 커피
- 영통외식
- 결항전문
- 푸르지오포레피스
- 양양솔비치아침
- 양양솔비치세프스키친
- 결항
- 편도수술
- 당근마켓중고차
- 중학교입학수학문제
- 홍시스무디
- 양양솔비치 뷔페
- 사진문자추출하기
- 영통역소고기
Archives
- Today
- Total
너와나의 관심사
백준 2580 스도쿠 문제 본문
백준 DFS 문제중에 스도쿠 문제로. backtracking 을 기본으로 하는 문제..
젤 어려웠던 부분은 .. count 를 하나하나 넘겨주면서 1~9 까지 값을 넣어 줘야 한다는걸 생각 + 구현해야한다는거다.
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | #include <stdio.h> #include <iostream> #include <memory.h> using namespace std; struct Pos{ int r; int c; }; Pos q[1000]; int arr[10][10]; int Num =0; void input(void){ for (int i = 0; i < 9; i++){ for (int j = 0; j < 9; j++){ cin >> arr[i][j]; //arr[i][j] = 0; if (arr[i][j] == 0){ q[Num].c = j; q[Num].r = i; Num++; } } } } // 세로 검사 bool chk_vertical(int r, int c, int num) { for (int row = 0; row < 9; row++) { if (arr[row][c] == num) return false; } return true; } // 가로 검사 bool chk_horizontal(int r, int c, int num) { for (int col = 0; col < 9; col++) { if (arr[r][col] == num) return false; } return true; } // 3x3 검사 bool chk_square(int r, int c, int num) { // 0-> 0 , 1-> 0, 2-> 0 // 3-> 1 , 4-> 1, 5-> 1 // 6-> 2 , 7-> 2, 8-> 2 r = r / 3; c = c / 3; for( int rr = r *3 ; rr < r *3 + 3; rr++){ for (int cc = c * 3; cc < (c * 3) + 3; cc++) { if (arr[rr][cc] == num) { return false; } } } return true; } //true -> end //false -> contiue; bool DFS(int idx){ if (idx == Num) { //print// for (int i = 0; i < 9; i++){ for (int j = 0; j < 9; j++){ cout << arr[i][j] << " "; } cout << "\n"; } return true; } else { int r = q[idx].r; int c = q[idx].c; for (int n = 1; n <= 9; n++){ if (chk_vertical(r, c, n) && chk_horizontal(r, c, n) && chk_square(r, c, n)){ arr[r][c] = n; if (DFS(idx + 1)) return true; arr[r][c] = 0; } } } return false; } int main() { int ret; freopen("input.txt", "r", stdin); setbuf(stdout, NULL); input(); int r = q[0].r; int c = q[0].c; for (int n = 1; n <= 9; n++){ if (chk_vertical(r, c, n) && chk_horizontal(r, c, n) && chk_square(r, c, n)){ arr[r][c] = n; if (DFS(1)) break; arr[r][c] = 0; } } return 0; } | cs |
Comments