본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 1941번 소문난 칠공주 이거 이틀이나 썼다. 원래 어제 풀었어야 했는데, 어제 두시간을 붙잡아도 풀지 못해서 오늘 다시 첨부터 짰다. 오늘도 오래 걸렸다. 짚고 넘어가야 할 하나가 있다. 이 문제에선 DFS(or BackTracking)이 두 종류가 사용되었다. 말 그대로 필요에 의해 두 가지로 활용되었다. 1. Arr[5][5] 행렬에서 7개를 뽑는 모든 경우의 수를 위한 DFS 5 x 5 행렬이 있을 때, 각 한번씩만 탐색해보는 경우의 수가 아니라, 7개를 뽑는 경우의 수. 조합이다. 매번 true / false를 토글해 가면서 뽑는다. 25개 중에서 7개를 뽑는 경우의 수. 대략 O(25C7)이 되겠다. visit[check] = true; DFS(i + 1) visit[check] = false; 2. Arr[5][5].. 2022. 6. 28.
[BaekJoon/백준] 1347번 미로 만들기 어째 좀 할만하다 싶더니, 실버3 문제였구나.. 명령어의 MAXIMUM 길이는 50이고, 모두 F일 때가 가장 긴 길이일 테니 나올 수 있는 가장 긴 가로 x 세로 는 50 x 50 이다. 따라서, Arr[101][101] 을 선언한 뒤에 ( => Arr[0][0] ~ Arr[100][100] ) 중앙인 Arr[50][50]부터 시작하게 되면, 절대 배열 밖을 벗어날 수 없다. 입력값을 그대로 이행하여 미로를 만들어 준 뒤에, 배열을 돌면서 min_x, min_y, max_x, max_y 를 계산해준다. 직사각형을 만들기 위해 최대 범위를 지정해 주는 것이다. 만들고 난 뒤에는 min_x, min_y, max_x, max_y 를 이용해서 반복문을 돌면서, 기존에 Arr[][] 안의 값이 '.' 인 경우 .. 2022. 6. 27.
[BaekJoon/백준] 2251번 물통 나는 DFS로 풀었는데, BFS로 정말 깔끔하게 푸신 분이 있어서.. 추가적으로 본문 맨 아래에 게시해야겠다. 핵심은, 무한 반복을 방지하기 위해 SnapShot 배열(A, B, C 물이 특정하게 채워져 있는 경우의 리스트)을 만들어 놓는 것이다. 그리고 이미 접근한 경우라면, dfs를 진행하지 않는 것이다. // key point : A . B . C 스냅샷이 똑같으면 그만둠. #include #include using namespace std; bool SnapShot[201][201][201]; int B_SIZE[3]; // 0 1 2 = A B C. 보틀 사이즈 int Bottle[3]; // 0 1 2 = A B C. 물이 들어있는 양 set s; void dfs(int index) { // .. 2022. 6. 26.
[BaekJoon/백준] 14891번 톱니바퀴 이번 문제에서 생각해야 될 핵심은, "비교∙판단은 회전하기 전에 모두 처리되는 거고, 회전하는 것은 모든 판단 이후에 하면 된다는 것." 회전하고 나서 비교를 하면 안되므로, 일단 재귀적으로 현재 상태에 대해 대한 회전 값을 모두 계산한 뒤에 나중에 회전해준다. 각 톱니바퀴는 벡터로 표현하여, 0 ~ 7 까지의 인덱스 안에 S N 값을 넣어주었고 톱니바퀴가 몇번째 이냐에 따라, 재귀를 어떻게 진행할지를 결정한다(ex. 1번 톱니바퀴는 앞으로만 검사, 뒤에는 톱니가 없음. 2번 톱니바퀴는 앞뒤로 검사.. ) 또한, visit을 이용하여 톱니바퀴 영향 계산이 무한반복으로 일어나지 않게 체크 처리해준다. 톱니바퀴를 나타내는 데에는 deque를 사용했다. 앞 뒤로 push pop이 가능한 자료구조이다. #inc.. 2022. 6. 26.
반응형

티스토리툴바