백트래킹 (5) 썸네일형 리스트형 [백준] 17406번: 배열 돌리기 4 (JAVA 풀이) 문제 https://www.acmicpc.net/problem/17406풀이이 문제를 풀어나간 순서를 간단히 말하자면 다음과 같다.1. 연산 순서 정하기2. 회전 연산하기3. 배열값 구하기 1. 연산 순서 정하기회전 연산이 여러개면, 연산을 수행한 순서에 따라 배열이 달라지기 때문에 연산 순서 조합을 모두 구해야한다.연산은 최대 6개이기때문에 배열을 미리 만들어놔서 입력받을때 배열에 차례로 저장해두었다.배열에 연산을 미리 저장해둔 이유는 배열의 인덱스를 이용하여 연산 순서 조합을 구하기 위함이다!연산순서는 dfs(백트래킹) 방법으로 구했다. 2. 회전 연산하기제일 많은 시간이 걸렸던 부분.. [SWEA] 1954번: 달팽이 숫자 문제를 연습한다면 좋을 것 같다..일단, 1번에서 정한 연산 순서에 따라 .. [백준] 14502번: 연구소 (C++ 풀이) 문제https://www.acmicpc.net/problem/14502 풀이다음과 같은 순서로 구현하였다. 1. dfs로 벽 3개가 위치할 수 있는 경우들을 찾았다.2. 벽 3개를 세울 때마다 bfs로 바이러스를 퍼뜨려본다.3. 안전영역의 개수를 센다. 코드https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/14502.cpp 결과 [백준] 14889번: 스타트와 링크 (C++ 풀이) 문제https://www.acmicpc.net/problem/14889 풀이완전탐색 dfs로 풀었다.특이하게도,, dfs안에 dfs가 돌도록 만들었는데바깥 dfs는 스타트팀과 링크팀을 나누는 용도로 만들었다.실제로는 스타트팀만 짜놓고 나머지 선택안된것들이 자동으로 링크팀이라고 하였다.팀이 짜여질때마다 능력치를 계산하는 두번째 dfs가 실행된다.스타트팀이 1 2 3 4 라고 할경우스타트팀의 능력치는 s[1][2] + s[2][1] + s[1][3] + s[3][1] + s[1][4] + s[4][1] + s[2][3] + ... 이런식으로 더해지기 때문이다.이 계산이 모두 끝나고 다음 팀을 짜기 직전에 스타트팀의 능력치와 링크팀의 능력치 차이를 min값으로 갱신해주면 된다. 코드https://github... [백준] 15663번: N과 M(9) (C++ 풀이) 문제https://www.acmicpc.net/problem/15663 풀이입력으로 다 다른 숫자가 들어가는 것이 아니라같은 숫자도 들어갈 수도 있는 문제이다.대신 같은 수열을 만들어선 안되므로dfs를 진행하면서 만든 수열은 set에 insert하였다.dfs 하면서 중복되는 수열을 만들어도set은 중복 저장을 하지 않으므로dfs탐색을 모두 마친 후set에 있는 것을 출력하기만 하면된다. 코드https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/15663.cpp 결과 [백준] 15657번: N과 M (8) (C++ 풀이) 문제https://www.acmicpc.net/problem/15657 풀이N과 M은 dfs탐색을 연습할 수 있는 시리즈다dfs의 기본 프레임은 이렇다. void dfs(매개변수) {if(dfs탐색을 끝낼 조건) dfs실행! (조건에 맞게 재귀적으로 dfs함수 부르기)} 매개변수에는 재귀적으로 dfs를 부를 때, 필요한 상태같은 것들을 같이 넘겨주고싶은 것을 넣는다.이 문제에서 나는 vector에 저장하면서 탐색조건을 걸었기 때문에 매개변수에 따로 넘겨줄 정보는 없었따.(조금 더 연습을 해봐야 dfs, 백트래킹, 재귀 등등에 대한 확신이 생길 것 같다...) 코드https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/15657.cpp 결과 이전 1 다음
