PCCP 모의1회 2번

문제 링크 :

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

나의 소스 코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> *ab;
bool visited[11];
int sum, maximum = -1;

void dfs(int col)
{
    if(col == (*ab)[0].size())
    {
        maximum = maximum < sum ? sum : maximum;
        return;
    }
    for(int i=0;i<(*ab).size();i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            sum += (*ab)[i][col];
            dfs(col+1);
            sum -= (*ab)[i][col];
            visited[i] = false;
        }
    }
}

int solution(vector<vector<int>> ability) {
    int answer = 0;
    ab = &ability;
    fill_n(visited, ability.size(), false);
    
    dfs(0);
    
    answer = maximum;
    return answer;
}

비슷한 문제
백준 15686 치킨 배달 https://www.acmicpc.net/problem/15686
https://github.com/dagreatjh359/excercises/blob/main/DFS/15686.c%2B%2B

생각을 해내는데 생각보다 오래 걸렸다.
DFS를 생각하는데 꽤 시간이 걸렸다. 특히 열을 기준으로 탐색을 할 시 자신이 지나갔던 행 번호는 뛰어 넘되, 재귀를 사용하므로 본 함수로 return시에는 꼭 원래 값으로 복원을 해주어야함이 중요했다.
분명 풀었던 문제였는데 라는 생각을 오래했다.