-
99클럽 코테 스터디 16일차 TIL / N-Queen(프로그래머스)Study(진행중)/항해99 2024. 8. 7. 02:17
오늘의 학습 키워드
- 알고리즘
- 완전 탐색
- 백트래킹
공부한 내용 본인의 언어로 정리하기
https://school.programmers.co.kr/learn/courses/30/lessons/12952
백트래킹을 이용한 완전탐색 문제를 풀었다.
공격 가능한지 판단하는 로직이 따로 있을 것 같아 종이에 적어가며 규칙을 찾았고,
이후에는 무식하기 현재 위치로부터 위에 놓은 체스말들을 보며 놓을 수 있는지를 판단했다.
풀이 과정은 다음과 같다.
1. 현재 y축으로부터 위에 모든 체스말들을 보며 x축에 놓을 수 있는지 판단
2. 이후 백트래킹 로직을 수행하며 깊이가 n이 될 때 까지 실행
풀이는 다음과 같다.
class Solution { int n, cnt = 0; int[] board; public int solution(int n) { this.n = n; board = new int[n + 1]; dfs(1); return cnt; } public void dfs(int depth) { if (depth == n + 1) { cnt++; return; } for (int x = 1; x <= n; x++) { boolean isPossable = true; for (int y = 1; y < depth; y++) { if (attackable(depth, x, y, board[y])) { isPossable = false; break; } } if (isPossable) { board[depth] = x; dfs(depth + 1); board[depth] = 0; } } } public boolean attackable(int y1, int x1, int y2, int x2) { if (x1 == x2) return true; if (y1 + x1 == y2 + x2) return true; if (y1 - x1 == y2 - x2) return true; return false; } }
반응형'Study(진행중) > 항해99' 카테고리의 다른 글
99클럽 코테 스터디 18일차 TIL / 일루미네이션(백준) (0) 2024.08.08 99클럽 코테 스터디 17일차 TIL / 사자와 토끼(백준) (0) 2024.08.07 99클럽 코테 스터디 15일차 TIL / 소수 찾기(프로그래머스) (0) 2024.08.06 99클럽 코테 스터디 14일차 TIL / 운영체제 - 프로세스 (0) 2024.08.05 99클럽 코테 스터디 13일차 TIL + 입국심사(프로그래머스) (0) 2024.08.04