완전 탐색
-
백준 13460 구슬 탈출 2Algorithm/BOJ 2020. 7. 24. 13:32
출처: www.acmicpc.net/problem/13460 분류: 완전 탐색 접근방식 상하좌우로 회전시킬 수 있는 보드판 위에 빨강, 파랑 구슬, 빠져나갈 구멍이 있을 때 움직여서 빨간 구슬만 구멍에 넣어야 할 때 최소 횟수를 찾는 문제입니다. 단, 횟수가 10번을 초과하면 안됩니다. 판의 크기가 3 ~ 10 까지로 매우 작고 10번이라는 제한이 있기 때문에 모든 경우를 다 탐색해서 말그대로 완전 탐색으로 해결할 수 있습니다. 개인적으로 구현이 꽤나 까다로웠던 문제였습니다. 상하좌우로 다 해본다는 게 말은 쉽지만 생각보다 까다로웠습니다. 두 구슬은 겹칠 수 없기 때문에 다른 구슬이 앞에 있다면 그 구슬 뒤까지 움직여야 하고 말이죠... 구현 아이디어는 다음과 같습니다. 빨간 구슬과 파란 구슬은 계속 굴..
-
백준 15683 감시Algorithm/BOJ 2020. 7. 16. 13:29
출처: www.acmicpc.net/problem/15683 분류: 완전탐색 접근방식 하.. 코드량이 너무 너무 너무 길었던 문제였습니다. 5개의 CCTV가 있고 각 CCTV는 90도로 회전이 가능합니다. 사각지대가 가장 최소가 되는 경우를 찾는 문제입니다. 각 CCTV 의 케이스는 1번 상하좌우 4개 2번 상하, 좌우 2개 3번 4개 4번 4개 5번 1개 입니다. 저는 CCTV를 먼저 찾아놓고 CCTV List를 다 탐색할 때 까지 DFS를 돌렸습니다. CCTV 에 케이스는 많지만 결국 지우는 건 방향에 따라 상하좌우 4가지 이므로 상하좌우 direction을 입력받는 함수를 만들어서 지우고 CCTV 타입별로 상 하 좌 우로 직접 입력해주는 방식을 사용했습니다. 더 스마트하게 풀 수도 있을 것 같은데 ..
-
백준 6603 로또Algorithm/BOJ 2020. 7. 15. 12:26
출처: www.acmicpc.net/problem/6603 분류: 완전 탐색 접근방식 주어진 문제에서 로또번호 6개를 골라서 출력하는 문제입니다. 전형적인 순열문제였습니다. 제 순열 관련 글도 있습니다 :) 위 글에서 사용한 스왑방식 대신 select 를 체크할 배열을 만들어서 인덱스만 넘겨주는 방식으로 풀었습니다. 스왑해서 재귀호출하고 다시 스왑을 한 번 더 해서 원상태로 바꿔주듯이 인덱스를 선택해서 true로 바꿔주고 호출한 다음에 다시 false로 바꾸고 호출해주는 과정이 필요합니다 ! 해결방법 func select(index: Int, count: Int) { //print("index: \(index), count: \(count)") if count == lottoNumberCount { fo..
-
백준 1065 한수Algorithm/BOJ 2020. 6. 15. 14:56
출처: www.acmicpc.net/problem/1065 분류: 완전 탐색 접근방식 주어진 N보다 작은 수 중에서 각 자리수가 등차수열을 이루는 수를 찾는 문제입니다. 등차 = 1의자리 수 - 10의자리수 와 같이 구할 수 있겠죠? 1의 자리 수 = n%10 10의 자리 수 = (n%100)/10 저는 이런 식으로 구했습니다. 해결방법 func isHansu(_ number: Int) -> Bool { if number 0 { if d != n - num%10{ return false } n = num%10 num /..