프로그래밍 공부/백뚠18 여인천하 (백준 9669번 : N-Queen) 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 재귀알고리즘의 대표 문제 중 하나인 퀸 문제다. 외판원 순환2랑 비슷하지만, 경우의 수가 더 많고 공간적으로 생각할 것이 더 많은 문제이다. - 대전략 : N * N 으로 체스판을 만들고, T/F로 구분한다. (퀸을 배치했거나 갈 수 없는 곳은 F) 우선 y=0인 곳에 퀸을 놓는다. 그 후, 다음 y열~N-1열에서 같은 x방향, 대각선을 모두 False한다. 그리고 다음 y열에서 x=0행부터 N-1행까지 True를 탐색하고, .. 2020. 12. 16. 이 세상의 모든 세일즈맨을 위하여 (백준 10971번 : 외판원 순회2) 10971번: 외판원 순회 2 (acmicpc.net) 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - 대전략 이 행렬에서 중요한 것은 도시의 시작점인 y=0(x[0])이다. 결국 이 문제도 N-Queen과 같은 문제가 아닐까. x=i, y=0 을 시작점으로 하고, 0 이 아닌 곳에 가는 경우의 수를 구현해본다. 그러면 for로 y=0을 돌린다. 그리고 안에서 재귀함수로 실행시켜야 할 것 같다. 만약 (0,0)에서 시작한다면 각각 (0,1) (0,2) (0,3) .. 2020. 12. 15. 날씨의 아이 (백준 2468번 : 안전 영역) 2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net - 대전략 (0,0)부터 탐색을 시작한다. 만약 (0,0)이 T(그림 상 흰색)라면 카운트 (안전영역) 갯수를 올리고, dx dy로 상하좌우에 방문해본다. 만약 경계선이거나 F라면은 그냥 놔두고, T인 곳을 방문한다. (재귀함수 실행) 그런데 여기는 카운트를 올리면 안되지 않는가? (이어진 곳이기 때문에) 이를 어떻게 처리할 것인가. 시작은 이중 for문으로 돌리고 탐색만 bfs로 처리할 것인가? 일단 시작해보자. 시작은.. 2020. 12. 15. 직사각형에서 탈출 보호되어 있는 글 입니다. 2020. 12. 11. 이전 1 2 다음
