일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- HTML5
- 백준
- 포이마웹
- 백준알고리즘
- 백준구현
- 프로그래머스
- 다이나믹프로그래밍
- 코딩테스트
- 백준구현문제
- CSS
- 리액트
- 백준nodejs
- 프로그래머스코테
- 리액트댓글기능
- 몽고DB
- dp알고리즘
- 코테
- 익스프레스
- JS프로그래머스
- 안드로이드 스튜디오
- 리액트커뮤니티
- js코테
- 프로그래머스JS
- JS
- 백준js
- 자바스크립트
- 백준골드
- 알고리즘
- css기초
- HTML
- Today
- Total
개발새발 로그
[JS] 백준 2580번 : 스도쿠 - 백트래킹, DFS 본문
https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
풀이방법
1. 스고쿠 맵안에서 0인 곳의 좌표를 모두 찾아 저장한다.
2. DFS를 호출해 카운트 0부터 시작한다
-이는 0인 곳에 숫자를 넣은 후 +1해서 다시 DFS를 재귀호출한다.
3. DFS를 0부터 시작했으므로 0인 곳의 좌표를 저장했던 배열도 인덱스 0부터 시작한다.
-0인 곳의 좌표를 순차적으로 뽑아내서 그 안에 숫자를 넣을 것이다.
4. 1 ~ 9까지의 숫자를 모두 넣어보고 가로열, 세로열, 3*3 부분에서 스도쿠가 성사되는지 확인한다.
5. 만약 성사된다면 map안에 그 값을 넣고 DFS를 count+1해서 재귀호출한다.
6. 이후 만약 해당 재귀호출이 어느 숫자에서 성사되지않는다면 백트래킹을 위해 다시 map에 숫자를 넣었던 좌표를 다시 0으로 만들어준다.
7. 이렇게 재귀호출을 뻗어나가면서 만약 성공적으로 0인 곳의 좌표에 모두 숫자를 넣었다면 스도쿠가 성사된 것이므로 해당 map을 출력하고 프로그램을 종료한다.
🤟내 제출
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");
let map = [];
for (var i = 0; i < 9; i++) {
map[i] = input[i].split(" ").map(Number);
}
let arr = [];
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
if (map[i][j] === 0) {
arr.push([i, j]);
}
}
}
let check = (y, x, value) => {
//가로 줄에서 같은 숫자 있는지
for (let i = 0; i < 9; i++) {
if (map[y][i] == value) return false;
}
//세로 줄에서 같은 숫자있는지
for (let i = 0; i < 9; i++) {
if (map[i][x] == value) return false;
}
//3*3도 맞는지
let threeX = Math.floor(x / 3) * 3;
let threeY = Math.floor(y / 3) * 3;
for (let i = threeY; i < threeY + 3; i++) {
for (let j = threeX; j < threeX + 3; j++) {
if (map[i][j] == value) return false;
}
}
return true;
};
let DFS = (count) => {
if (count == arr.length) {
console.log(map.map((v) => v.join(" ")).join("\n"));
process.exit(0);
}
let [y, x] = arr[count];
//숫자 1~9를 그냥 넣어서 맞는지 확인
for (let i = 1; i < 10; i++) {
if (check(y, x, i)) {
map[y][x] = i;
DFS(count + 1);
map[y][x] = 0;
}
}
};
DFS(0);
💢어려웠던 점
1. DFS의 기준을 어떻게 잡을지 파악하지 못했다.
-가로열 세로열 3*3부분을 확인하고 재귀로 뻗어나가야 하는데 1~9까지 모든 수를 넣어보면서 확인하는 방법을 생각하지 못했다.
-그저 가로열 세로열 3*3 확인해서 정답인 숫자를 넣는다는 생각만했다.
'알고리즘' 카테고리의 다른 글
[JS] 백준 2110번 : 공유기 설치 - 이분 탐색 (0) | 2023.08.15 |
---|---|
[JS] 백준 1806번 : 부분합 - 누적 합, 투 포인터, 효울성 (0) | 2023.08.14 |
[JS] 백준 1107번 : 리모컨 - 브루투포스, 완전탐색 (0) | 2023.08.08 |
[JS] 백준 17298번 - 오큰수 - 스택, 자료구조 (0) | 2023.08.07 |
[JS] 백준 1978 : 알파벳 - 그래프, 이론그래프, 탐색, 깊이 우선 탐색,백트래킹 (0) | 2023.08.01 |