완전탐색
-
백준 14500 테트로미노Algorithm/BOJ 2020. 7. 15. 14:07
출처: www.acmicpc.net/problem/14500 분류: 완전 탐색 접근방식 주어진 5개의 테트로미노를 하나 놓을 때 테트로미노에 겹쳐지는 블록의 최대값이 얼마인지 구하는 문제입니다. 모든 경우를 다 체크하면 되겠지만 테트로미노는 회전 또는 대칭이 되기 때문에... 매우매우 귀찮습니다.. 😨 하지만 이 문제에는 귀찮음을 덜어줄 수 있는 법칙이 숨겨져 있습니다 :) 바로 ㅗ 모양을 제외한 테트로미노들은 한 점에서 dfs로 4개씩 탐색한 결과들입니다. 한 점에서 dfs로 4개의 블록을 고르면 4개의 테트로미노를 회전 대칭 시킨 모양안에 모두 포함됩니다! 대신 ㅗ 모양은 ㅗ ㅜ ㅏ ㅓ를 따로 찾아줘야 합니다. 해결방법 let nm = readLine()!.split(separator: " ").ma..
-
백준 15686 치킨 배달Algorithm/BOJ 2020. 7. 13. 18:42
출처: www.acmicpc.net/problem/15686 분류: 완전탐색 접근방식 집과 치킨집이 주어지고 집에서 제일 가까운 치킨집까지의 거리가 집의 치킨거리가 됩니다. 모든 집의 치킨 거리를 합친 값이 도시의 치킨거리가 됩니다. 치킨집을 M개 만큼 선택했을 때 최소가 되는 치킨거리를 구하는 문제입니다. 우선 집과 치킨집의 위치를 먼저 저장해두고 치킨집을 M개 골랐을 때의 치킨 거리들을 구하면 됩니다. 해결방법 let nm = readLine()!.split(separator: " ").map{Int($0)!} var board = [[Int]]() for _ in 0..