룰루랄라 알고리즘

문제를 푼 시간의 9/10을 문제를 잘못 이해하고 풀었다. 이러한 좌표 DFS 문제를 좋아하는데 오랜만에 풀어서 감을 잃어서 고생했다. 이 문제의 핵심은 치즈를 기준으로 DFS를 돌리는 것이 아니라 공기를 기준으로 DFS를 돌리는 것이다. 또한 뒤통수를 한 대 맞은듯한 기분이든 fake가 있었는데 좌표의 가장자리 부분에는 치즈가 놓여있지 않는다는 부분이다. 이러한 문장의 의미는 좌표의 (0,0)이 무조건 공기라는 것이다. 예전 c로쓴 자료구조를 공부할 때 미로 찾기 알고리즘을 배웠었는데 해당 문제에서는 일부러 가장자리 좌표, 즉 좌표를 2개씩 늘려서 문제를 풀었다. 하지만 이 문제는 그러한 수고를 덜어주도록 처음부터 좌표에 제한된 부분을 포함시켜 주었다. https://www.acmicpc.net/pro..

백준 14888번 내 기준 dfs를 활용한 백트래킹 정석 문제 1. modify 리스트에 연산자의 개수를 저장 2. dfs 함수로 깊이 depth, 총 점수 total, 연산자의 개수를 변수로 넘김 3. 깊이가 N이 될 때 마다 total의 최댓값, 최솟값을 저장하고 함수를 빠져나오면 깊이가 N-1인 다른 dfs 함수가 실행되어 또 다시 total의 최대,최소 판별 4. 이렇게 모든 경우의 수를 백트래킹으로 판별가능

원래는 브루트 포스로 하나하나 대입해서 풀었는데 코드도 더럽고 내 취향이 아니라 다르게 풀어봤음 DFS를 이용하여 값을 더해가는 풀이 idx = 1 일 때(즉, 두개의 블럭을 선택했을 때) 새로운 블럭에서 다음 블럭을 탐색하는 것이 아니라 다시 기존블럭에서 탐색하게 만들면 ㅗ,ㅏ,ㅓ,ㅜ 모양을 만들 수 있다. 가지치기 하는 코드 2차원배열에서 최대값을 찾아서 max(map(max, graph)) 선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고 현재 누적합 total 에 더해서 max_result 와 비교해주는 방식 가지치기 안하니까 시간초과 나옴 ***방문처리 주의하자***

그래프의 순환을 구해서 나머지 트리에서 순환그래프까지의 거리 구하기

-1 : 아직 한 번도 탐색하지 않은 좌표 0 : 목표 지점까지 경로가 없는 좌표 그리고 목표 지점까지 갈 수 있는 좌표라면, 방문한 횟수에 따라 수가 올라갈 것이다. 1. dp 테이블을 -1로 초기화 한 후 dfs함수를 돌려 만약 x,y가 M-1,N-1 즉 좌표의 도착점 까지 도달한다면 1을 리턴하여 더해준다. 2. x,y의 좌표가 -1이 아니라면 방문 한 적이 있는 좌표므로 그 값을 리턴하여 더해준다. 3. 일단 좌표를 0으로 초기화 해서 4방향 dfs를 수행하여도 갈 수 있는 곳이 없다면 0을 리턴 4. 경로가 있다면 정상적으로 dfs를 수행. 5. 출발지가 결국 경로의 수가 됨 dp테이블 [3, 2, 2, 2, 1] [1, -1, -1, 1, 1] [1, -1, -1, 1, -1] [1, 1, 1..